栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 面试经验 > 面试问答

poj 1611 The Suspects

面试问答 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

poj 1611 The Suspects

#include <stdio.h>#include <iostream>using namespace std;const int MAXN = 30001; int pa[MAXN];    int rank[MAXN];    int num[MAXN];void make_set(int x){    pa[x] = x;    rank[x] = 0;    num[x] = 1;}int find_set(int x){        int r = x, temp;        while(pa[r] != r) r = pa[r];    while(x != r)    {        temp = pa[x];        pa[x] = r;        x = temp;    }    return x;    //if(x != pa[x]) //注释掉的其实也是可以的,不过不想用递归来做啦    //    pa[x] = find_set(pa[x]);    //return pa[x];}void union_set(int x, int y){    x = find_set(x);    y = find_set(y);    if(x == y)return ;    if(rank[x] > rank[y])    {        pa[y] = x;        num[x] += num[y];    }    else     {        pa[x] = y;        if(rank[x] == rank[y]) rank[y]++;        num[y] += num[x];    }}int main(){    int n, m, x, y, i, t, j;    while(scanf("%d%d", &n, &m))    {        if(m==n && n == 0) break;        if(m == 0)        { cout << "1n"; continue;        }        for(i = 0; i < n; i++) make_set(i);        for(i = 0; i < m; i++)        { scanf("%d", &t); scanf("%d", &x); for(j = 1; j < t; j++){     scanf("%d", &y);     union_set(x, y);     x = y; }        }        x = find_set(0);        cout << num[x] << endl;    }    return 0;}
转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/367853.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号