「BZOJ1370」[Baltic2003] Gang团伙
Description
在某城市里住着n个人，任何两个认识的人不是朋友就是敌人，而且满足： 1、 我朋友的朋友是我的朋友； 2、 我敌人的敌人是我的朋友； 所有是朋友的人组成一个团伙。告诉你关于这n个人的m条信息，即某两个人是朋友，或者某两个人是敌人，请你编写一个程序，计算出这个城市最多可能有多少个团伙？
Input
第1行为n和m，N小于1000,M小于5000； 以下m行，每行为p x y，p的值为0或1，p为0时，表示x和y是朋友，p为1时，表示x和y是敌人。
Output
一个整数，表示这n个人最多可能有几个团伙。
Sample Input
6
4
E 1 4
F 3 5
F 4 6
E 1 2
4
E 1 4
F 3 5
F 4 6
E 1 2
Sample Output
3
HINT
{1},{2,4,6},{3,5}
题解
裸并查集
使用拆点的方法，若a，b为朋友，将a与b所在集合合并，这样符合我朋友的朋友是我的朋友
若为敌人，则将a与b’，a’与b合并，这样符合我敌人的敌人是我的朋友
即a与b为敌，b与c为敌，会将a与c所在集合合并
最后统计1-n属于的集合个数即可
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 |
#include<iostream> #include<set> #include<map> #include<cstdio> #include<cstring> #include<cstdlib> #include<ctime> #include<vector> #include<queue> #include<algorithm> #include<cmath> #define inf 2000000000 #define pa pair<int,int> #define ll long long using namespace std; ll read() { ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n,m,ans; int fa[2005],a[2005]; int find(int x) { return x==fa[x]?x:fa[x]=find(fa[x]); } int main() { n=read();m=read(); for(int i=1;i<=2*n;i++)fa[i]=i; for(int i=1;i<=m;i++) { char ch[5];scanf("%s",ch); int x=read(),y=read(); if(ch[0]=='F')fa[find(x)]=find(y); else fa[find(x)]=find(y+n),fa[find(y)]=find(x+n); } for(int i=1;i<=n;i++)a[i]=find(i); sort(a+1,a+n+1); for(int i=1;i<=n;i++) if(a[i]!=a[i-1]) ans++; printf("%d",ans); return 0; } |
计数器 9773995
OI 课件=>
OI 课件=>
代码里的a[i] == 1应该i == 1吧
已更正