poj 1161 The Suspects

87 阅读 0 评论 58 点赞

我是靠谱客的博主顺心铃铛，这篇文章主要介绍poj 1161 The Suspects，现在分享给大家，希望可以做个参考。

题目链接： The Suspects

题目大意：给你一个n和m，代表有n个人，m个朋友团体，每个团体有k个人，朋友的朋友也是朋友，问最后跟0在一个朋友集合里面的人有多少个（包括0本身）

题目思路：并查集，直接连，连完之后判断就好

复制代码

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
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <algorithm>
#include <set>
#include <map>
#include <vector>

using namespace std;

int n,m,k,a,b,pre[100005];

int Find(int x){
    if(x == pre[x]) return x;
    return pre[x] = Find(pre[x]);
}

void join(int x,int y){
    int p = Find(x);
    int q = Find(y);
    if(p != q) pre[q] = p;
}

int main(){
    while(~scanf("%d%d",&n,&m)&&n+m){
        for(int i = 0;i < n;i++)
            pre[i] = i;
        while(m--){
            scanf("%d",&k);
            scanf("%d",&a);
            for(int i = 1;i < k;i++)
                scanf("%d",&b),join(a,b);
        }
        int ans = 0;
        for(int i = 0;i < n;i++){
            if(Find(i) == Find(0))
                ans++;
        }
        printf("%dn",ans);
    }
    return 0;
}