bzoj1370 [Baltic2003]Gang团伙-白红宇

bzoj1370 [Baltic2003]Gang团伙

阅读量：5269 次

发布时间：2019-06-14

本文共 1496 字，大约阅读时间需要 4 分钟。

一道水题

把一个人分为两种人格：作为朋友时(i)；作为敌人时(i+n)

拆点并查集维护关系

注意统计答案时要先find之后取个数而不是找fa[i]==i(1<=i<=n)的个数

因为一些人只作为敌人出现过所以find的结果可能是作为敌人的人格就统计不到，所以要先find

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 #include
         
           6 #include
          
            7 #include
           
             8 #include
            
              9 #include
             
              10 #include
              
               11 #include
               12 #include
                
                 13 #define rre(i,r,l) for(int i=(r);i>=(l);i--)14 #define re(i,l,r) for(int i=(l);i<=(r);i++)15 #define Clear(a,b) memset(a,b,sizeof(a))16 #define inout(x) printf("%d",(x))17 #define douin(x) scanf("%lf",&x)18 #define strin(x) scanf("%s",(x))19 #define LLin(x) scanf("%lld",&x)20 #define op operator21 #define CSC main22 typedef unsigned long long ULL;23 typedef const int cint;24 typedef long long LL;25 using namespace std;26 void inin(int &ret)27 {28 ret=0;int f=0;char ch=getchar();29 while(ch<'0'||ch>'9'){ if(ch=='-')f=1;ch=getchar();}30 while(ch>='0'&&ch<='9')ret*=10,ret+=ch-'0',ch=getchar();31 ret=f?-ret:ret;32 }33 int n,m,fa[2020];34 int find(int x){ return x==fa[x]?x:fa[x]=find(fa[x]);}35 int CSC()36 {37 inin(n),inin(m);38 re(i,1,n<<1)fa[i]=i;39 re(i,1,m)40 {41 char s[4];42 int q,w;43 strin(s);inin(q),inin(w);44 if(s[0]=='E')fa[find(q)]=find(w+n),fa[find(w)]=find(q+n);45 else fa[find(q)]=find(w);46 }47 int ans=0;48 re(i,1,n)fa[i]=find(i);49 sort(fa+1,fa+n+1);50 re(i,1,n)if(fa[i]!=fa[i-1])ans++;51 printf("%d",ans);52 return 0;53 }