rqnoj 577 团伙


		终于找到这题的提交链接了，刘汝佳那本书81页有这题的的题解，不重复了。
我觉得这题思维还是很饶人的。
题目大体的说：
1.我朋友的朋友是我的朋友；
 2.我敌人的敌人是我的朋友；
所有是朋友的人组成一个团伙。告诉你关于这N个人的M条信息，即某两个人是朋友，或者某两个人是敌人，请你编写一个程序，计算出这个城市最多可能有多少个团伙？
用并查集来记录，其中e[i]记录i的是i的敌人组成的团伙。
[cpp]  
#include <iostream>  
#include <stdio.h>  
#include <stdlib.h>  
#include <string.h>  
#include <math.h>  
#include <algorithm>  
#include <stack>  
#include <queue>  
#include <map>  
using namespace std;  
  
int f[1005];  
int e[1005];  
int vis[1005];  
  
int findset(int a)  
{  
    if(a == f[a])  
    {  
        return a;  
    }  
    f[a] = findset(f[a]);  
    return f[a];  
  
}  
void unionset(int a,int b)  
{  
    a = findset(a);  
    b = findset(b);  
    if(a!=b)  
    {  
        f[b] = a;  
    }  
}  
int main()  
{  
    /*#ifndef ONLINE_JUDGE 
        freopen("in.txt","r",stdin); 
    #endif*/  
    int n,m;  
    char c;  
    int a,b;  
    while(scanf(" %d %d",&n,&m)!=EOF)  
    {  
        memset(e,0,sizeof(e));  
        memset(vis,0,sizeof(vis));  
  
        for(int i=1; i<=n; i++)  
        {  
            f[i] = i;  
        }  
        for(int i=0; i<m; i++)  
        {  
            scanf(" %c %d %d",&c,&a,&b);  
            //printf("c = %c\n",c);  
            if(c == 'F')  
            {  
                unionset(a,b);  
            }  
            else if(c == 'E')  
            {  
                if(e[a] == 0)  
                {  
                    e[a] = b;  
                }  
                else  
                {  
                    unionset(e[a],b);  
                }  
                if(e[b] == 0)  
                {  
                    e[b] = a;  
                }  
                else  
                {  
                    unionset(e[b],a);  
                }  
            }  
        }  
        int sum = 0;  
        for(int i=1; i<=n; i++)  
        {  www.zzzyk.com
            int cur = findset(i);  
            if(vis[cur] == 0)  
            {  
                vis[cur] = 1;  
                sum++;  
            }  
        }  
        printf("%d\n",sum);  
    }  
    return 0;  
}

补充：软件开发 , C++ ,