BZOJ 1370 [Baltic2003]Gang团伙 并查集

题意: 朋友的朋友是我的朋友，敌人的敌人是我的朋友。 n(<=1000)个人给出m(<=5000)对关系表示谁与谁是朋友关系或者是敌对关系。 询问这n个人最多分多少团伙。 解析: 原来做的那个是这个的弱化版…只有朋友关系…. 然后这个的话敌对关系我们可以用一种巧妙地拆点法，注意这个方法也是为了秉行上面的那个朋友的朋友….. 朋友关系我们直接合并即可。 敌对关系的话，我们可以考虑把x拆成x与x+n,x+n如果代表与x敌对的话，恰好可以满足我们秉行的那句话，，然后最后我们统计一下所有点有多少个不同的团伙即可。 挺有意思的拆点法… 另外，我尝试封装了下并查集，感觉萌萌哒。 代码:

;class Union_Find_Set{public:int fa[N];Union_Find_Set(int n){for(int i=1;i<=n;i++)size[i]=1,fa[i]=i;}int find(int x){if(fa[x]==x)return x;return fa[x]=find(fa[x]);}void Union(int x,int y){x=find(x),y=find(y);if(x!=y){if(size[x]>size[y])swap(x,y);fa[x]=y;size[y]+=size[x];}}private:int size[N];}UFS(N-1);int n,m;char s[2];int a[N];int main(){scanf(“%d%d”,&n,&m);for(int i=1;i<=m;i++){int x,y;scanf(“%s%d%d”,s,&x,&y);if(s[0]==’E’)UFS.Union(x+n,y),UFS.Union(y+n,x);else UFS.Union(x,y);}for(int i=1;i<=n;i++)a[i]=UFS.find(i);sort(a+1,a+n+1);int ans=0;for(int i=1;i<=n;i++)if(a[i]!=a[i-1])ans++;printf(“%d\n”,ans);}

青春一经典当即永不再赎