今天去杭电做了两道题，主要是看了杭电并查集的讲义。 感觉他讲得非常棒，纯入门了。 也在今天又学了一个新的知识，并查集，感到很高兴。 HDU1272 题目意思是找到判断是不是连通无环的图。 判断成环的时候，只要判断输入边的两个点。有一个共同的父节点，那么这两个点就成环。 判断连通的时候，只要判断根节点数为1即可。 不多说，简单题，上代码。 上代码。 #include <stdio.h>#include <string.h>int k,flag[100005],bin[100005];int find(int x){    if(bin[x] == x)  return x;    return bin[x] = find(bin[x]);}void merge(int x,int y){    int fx,fy;    fx = find(x);    fy = find(y);    if(fx != fy)        bin[fx] = fy;    else        k = 0;}int main(){    int i,j,n,m,cnt,p;    while(scanf("%d%d",&n,&m) != EOF && n != -1)    {        if(n == 0)        {            puts("Yes");            continue;        }        for(i = 1;i <= 100001;i++)        {            flag[i] = 0;            bin[i] = i;        }        flag[n] = flag[m] = 1;        k = 1;        merge(n,m);        while(scanf("%d%d",&n,&m) != EOF && n != 0)        {            merge(n,m);            flag[n] = flag[m] = 1;        }        cnt = 0;        for(i = 1;i <= 100001;i++)        {            if(flag[i] && bin[i] == i)                cnt++;            if(cnt > 1)                k = 0;        }        if(k)            printf("Yes\n");        else            printf("No\n");    }    return 0;}

评论