[关闭]
@fuheimao 2014-10-16T06:59:03.000000Z 字数 597 阅读 39

Gangs

腹黑猫


  1. #include<iostream>
  2. #include<cstdio>
  3. using namespace std;
  4. int f[1001];
  5. int e[1001];
  6. int a[1001]={0};
  7. bool vis[1001];
  8. int find(int x){
  9. return (f[x]==x?x:f[x]=find(f[x]));
  10. }
  11. int setfather(int x,int y){
  12. f[find(x)]=find(y);
  13. }
  14. int main (){
  15. freopen("gangs.in","r",stdin);
  16. freopen("gangs.out","w",stdout);
  17. int n,m;
  18. cin>>n>>m;
  19. for (int i=1;i<=n;i++){
  20. f[i]=i;
  21. e[i]=0;
  22. }
  23. for (int i=1;i<=m;i++){
  24. char a;
  25. int x,y;
  26. cin>>a>>x>>y;
  27. if (a=='E'){ //敌人
  28. if (e[x]==0){
  29. e[x]=y;
  30. }else{
  31. setfather(e[x],y);
  32. }
  33. if (e[y]==0){
  34. e[y]=x;
  35. }else{
  36. setfather(e[y],x);
  37. }
  38. }else{//朋友
  39. setfather(x,y);
  40. }
  41. }
  42. int ans=0;
  43. for (int i=1;i<=n;i++){
  44. if (!vis[find(i)]){
  45. ans++;
  46. vis[find(i)]=true;
  47. }
  48. }
  49. cout<<ans<<endl;
  50. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注