题目描述 Description
1920年的芝加哥,出现了一群强盗。如果两个强盗遇上了,那么他们要么是朋友,要么是敌人。而且有一点是肯定的,就是:
我朋友的朋友是我的朋友;
我敌人的敌人也是我的朋友。
两个强盗是同一团伙的条件是当且仅当他们是朋友。现在给你一些关于强盗们的信息,问你最多有多少个强盗团伙。
输入描述 Input Description
输入文件gangs.in的第一行是一个整数N(2<=N<=1000),表示强盗的个数(从1编号到N)。 第二行M(1<=M<=5000),表示关于强盗的信息条数。 以下M行,每行可能是F p q或是E p q(1<=p q<=N),F表示p和q是朋友,E表示p和q是敌人。输入数据保证不会产生信息的矛盾。
输出描述 Output Description
输出文件gangs.out只有一行,表示最大可能的团伙数。
样例输入 Sample Input
6 4 E 1 4 F 3 5 F 4 6 E 1 2
样例输出 Sample Output
3
数据范围及提示 Data Size & Hint
2<=N<=1000
1<=M<=5000
1<=p q<=N
1 #include<cstdio>
2 #include<iostream>
3 #include<cstdlib>
4 #include<cmath>
5 #include<cstring>
6 using namespace std;
7 long fa[1001],a[1001][1001],c[1001];
8 long find(long x)
9 {
10 long r;
11 r=x;
12 while (fa[r]!=r) r=fa[r];
13 return r;
14 }
15 int main()
16 {
17 long n,m,s=0,i,j,k,x,y,r1,r2,t;
18 char z;
19 cin>>n>>m;
20 memset(a,0,sizeof(a));
21 for (i=1; i<=n; i++)
22 fa[i]=i;
23 for (i=1; i<=m; i++)
24 {
25 cin>>z>>x>>y;
26 if (z=='F')
27 {
28 r1=find(x);
29 r2=find(y);
30 fa[r2]=r1;
31 }
32 if (z=='E') // x,y为敌对关系
33 {
34 for (j=1; j<=a[x][0]; j++) //a[x][0]为x敌人的数量
35 {
36 r1=find(y);
37 r2=find(a[x][j]);
38 fa[r2]=r1;
39 }
40 for (j=1; j<=a[y][0]; j++)
41 {
42 r1=find(x);
43 r2=find(a[y][j]);
44 fa[r2]=r1;
45 }
46 a[x][0]++;
47 a[y][0]++;
48 a[x][a[x][0]]=y;
49 a[y][a[y][0]]=x;
50 }
51 }
52 s=0;
53 for (i=1; i<=n; i++)
54 if (fa[i]==i)
55 s++;
56 cout<<s;
57 }
58