连通图

连通图

http://www.nowcoder.com/questionTerminal/569e89823a5141fe8a11ab7d4da21edf

妈妈我终于学会并查集啦!

#include<stdio.h>
int father[1005] = {0};
void init(int father[])
{
    for(int i = 0;i<1005;i++)
        father[i] = i;
    return;
}
int findfather(int n)
{
    if(father[n] == n)
        return n;
    else
        return findfather(father[n]);
}

int main()
{
    int n,m;
    int x,y;
    while(scanf("%d",&n) != EOF &&n)
    {
        scanf("%d",&m);
        init(father);
        for(int i = 0;i<m;i++)
        {
            scanf("%d%d",&x,&y);
            // 合并
            int fx = findfather(x);
            int fy = findfather(y);
            if(fx != fy)
                father[fx] = fy;
        }
        int f = findfather(1); // 以1为起点
        int flag = 1;
        for(int i = 1;i <= n;i++) // 判断是否连通
        {
            if(findfather(i) != f)
            {
                flag = 0;
                break;
            }
        }
        if(flag)
            printf("YES\n");
        else
            printf("NO\n");
    }
    return 0;
}
全部评论

相关推荐

点赞 评论 收藏
分享
2 收藏 评论
分享
牛客网
牛客企业服务