POJ1611 The Suspects [ 数据结构-并查集 union-find sets]

Categories: 数据结构和算法
Comments: No Comments
Published on: 2011 年 03 月 23 日

水题毫无压力,不解释。简单理解下并查集流程。

不同意的请看之前发的,并学习并查集

#include <cstdio>  
using namespace std;  
const int MAXSIZE = 30001;  
int pre[MAXSIZE]; //根节点i,pre[i] = -num,其中num是该树的节点数目;  
//非根节点j,pre[j] = k,其中k是j的父节点  
int Find(int x){//查找+非递归的路径压缩  
    int p = x;  
    while( pre[p] > 0 )    p = pre[p];  
    while( x != p ){  
        int temp = pre[x]; pre[x] = p; x = temp;  
    }  
    return x;  
}  
void Union(int r1, int r2){  
    int a = Find(r1); int b = Find(r2);  
    if( a == b ) return ;  
    //加权规则合并  
    if( pre[a] < pre[b] ){  
        pre[a] += pre[b]; pre[b] = a;  
    }  
    else {  
        pre[b] += pre[a]; pre[a] = b;  
    }  
}  
void Initi(int n)  
{  
    for( int i=0; i <= n; ++i ) pre[i] = -1;  
}  
int main()  
{  
    //freopen("1.txt","r",stdin);  
    int n,m;  
    int x,temp1,temp2;  
    while(scanf("%d%d",&n,&m)!=EOF)  
    {  
        if(n==0 && m==0) break;  
        Initi(n);  
        for (int i=0;i<m;i++)  
        {  
            scanf("%d",&x);  
            scanf("%d",&temp1);  
            for (int j=0;j<x-1;j++)  
            {  
                scanf("%d",&temp2);  
                Union(temp1,temp2);  
            }  
        }  
        printf("%d\n",-pre[Find(0)]);  
    }  
}  

我猜你可能也喜欢:

No Comments - Leave a comment

Leave a comment

电子邮件地址不会被公开。 必填项已用*标注

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>


Welcome , today is 星期二, 2017 年 10 月 24 日