codevs 2597 团伙

题目描述

1920年的芝加哥，出现了一群强盗。如果两个强盗遇上了，那么他们要么是朋友，要么是敌人。而且有一点是肯定的，就是：

我朋友的朋友是我的朋友；

我敌人的敌人也是我的朋友。

两个强盗是同一团伙的条件是当且仅当他们是朋友。现在给你一些关于强盗们的信息，问你最多有多少个强盗团伙。

输入描述

输入的第一行是一个整数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是敌人。输入数据保证不会产生信息的矛盾。

输出描述

输出只有一行，表示最大可能的团伙数。

样例输入

6
4
E 1 4
F 3 5
F 4 6
E 1 2

样例输出

3

解题思路

　　这道题的有趣的地方在“敌人的敌人是朋友”；

　　这题我刚开始将关系为朋友的进行合并，但是关系为敌人的进行存储，在所有的关系为敌人内双重循环进行合并，数据比较水，过了；

　　参考方法：codevs 2597 团伙

　　f[]数组维护并查集，e[i]数组维护 i 的敌人的代表；

代码如下：

 1 #include<iostream>
 2 using namespace std;
 3 int n, m, pre[5010];
 4 struct node{
 5     int x, y, fx, fy;
 6 }no[10010];
 7 void init(){
 8     for(int i = 1; i <= n; i++)    pre[i] = i;
 9 }
10 int getf(int v){
11     if(pre[v] == v) return v;
12     else    return pre[v] = getf(pre[v]);
13 }
14 void meg(int v, int u){
15     int t1 = getf(v), t2 = getf(u);
16     if(t1 != t2)    pre[t2] = t1;
17 }
18 int main(){
19     cin >> n >> m;
20     int cnt = 0;
21     init(); 
22     for(int i = 1; i <= m; i++){
23         char f;
24         int x, y;
25         cin >> f >> x >> y;
26         if(f == 'F')    meg(x, y); 
27         if(f == 'E')    no[cnt].x = x, no[cnt].y = y, cnt++;
28     }
29     for(int i = 0; i < cnt; i++){
30         no[i].fx = 1, no[i].fy = 1;
31         for(int j = 0; j < cnt; j++){
32             if(no[i].x == no[j].x && no[j].fx == 0){
33                 no[j].fx = 1;
34                 meg(no[i].y, no[j].y);
35             }
36              if(no[i].y == no[j].y && no[j].fy == 0){
37                  no[j].fy = 1;
38                  meg(no[i].x, no[j].x);
39              }
40         }
41     }
42     int sum = 0;
43      for(int i = 1; i <= n; i++){
44          if(pre[i] == i)    sum++;
45      }
46      cout << sum << endl;
47     return 0;
48 }

暴力

 1 #include<iostream>
 2 using namespace std;
 3 const int Max = 100000;
 4 int n, m, f[Max], e[Max];
 5 void init(){
 6     for(int i = 1; i <= n; i++)    f[i] = i;
 7 }
 8 int getf(int v){
 9     if(f[v] == v)    return v;
10     else    return f[v] = getf(f[v]);
11 }
12 void meg(int v, int u){
13     int t1 = getf(v), t2 = getf(u);
14     if(t1 != t2)    f[t2] = t1;
15 }
16 int main(){
17     cin >> n >> m;
18     init();
19     for(int i = 1; i <= m; i++){
20         char c;
21         int x, y;
22         cin >> c >> x >> y;
23         if(c == 'F')    meg(x, y);
24         if(c == 'E'){
25             if(e[x] == 0)    e[x] = getf(y);
26             else    meg(e[x], y);
27             if(e[y] == 0)    e[y] = getf(x);
28             else    meg(e[y], x);
29         }
30     } 
31     int sum = 0;
32     for(int i = 1; i <= n; i++){
33         if(f[i] == i)    sum++;
34     }
35     cout << sum << endl;
36     return 0;
37 }

参考方法