题面:
1920年的芝加哥,出现了一群强盗。
如果两个强盗遇上了,那么他们要么是朋友,要么是敌人。
而且有一点是肯定的,就是:
我朋友的朋友是我的朋友;
我敌人的敌人也是我的朋友。
两个强盗是同一团伙的条件是当且仅当他们是朋友。
现在给你一些关于强盗们的信息,问你最多有多少个强盗团伙。
输入格式
第一行包含整数N,表示强盗的个数(从1编号到N)。
第二行包含整数M,表示关于强盗的信息条数。
接下来M行,每行可能是F p q或是E p q,F表示p和q是朋友,E表示p和q是敌人。
输入数据保证不会产生信息的矛盾。
输出格式
输出只有一行,表示最大可能的团伙数。
数据范围
2≤N≤10002≤N≤1000,
1≤M≤50001≤M≤5000,
1≤p,q≤N1≤p,q≤N
输入样例
6
4
E 1 4
F 3 5
F 4 6
E 1 2
输出样例
3
题解:
理解
1.朋友的朋友是我的朋友
2.敌人的敌人是我的朋友;
3.敌人的朋友和我关系不确定
代码
#include<iostream> #include<cstring> #include<algorithm> #include<cstdio> using namespace std; int fa[1010],f[1010],vis[1010];//f数组存敌人 int find(int x) { return fa[x]==x?x:fa[x]=find(fa[x]); } void uoion1(int x,int y) { x=find(x); y=find(y); if(x==y) return; fa[x]=y; } int main() { int n,m;char ch;int x,y; scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) fa[i]=i; while(m--) { cin>>ch>>x>>y; if(ch=='F') { uoion1(x,y); } else { if(!f[x])//a没有敌人, f[x]=y; else uoion1(y,f[x]); if(!f[y]) f[y]=x; else uoion1(x,f[y]); } } int cnt=0; for(int i=1;i<=n;i++) { if(!vis[find(i)]) { cnt++; vis[find(i)]=1; } } printf("%d\n",cnt); return 0; }