小鑫的城堡——并查集

╰+哭是因爲堅強的太久メ 2022-07-12 09:58 108阅读 0赞

hint:  
1是否有多个根结点  
2是否有回路存在

[sdut原题链接][sdut]

小鑫的城堡  
Time Limit: 1000MS Memory Limit: 65536KB

Problem Description  
从前有一个国王，他叫小鑫。有一天，他想建一座城堡，于是，设计师给他设计了好多简易图纸，主要是房间的连通的图纸。小鑫希望任意两个房间有且仅有一条路径可以相通。小鑫现在把设计图给你，让你帮忙判断设计图是否符合他的想法。比如下面的例子，第一个是符合条件的，但是，第二个不符合，因为从5到4有两条路径（5-3-4和5-6-4）。

Input  
多组输入，每组第一行包含一个整数m（m < 100000），接下来m行，每行两个整数，表示了一条通道连接的两个房间的编号。房间的编号至少为1，且不超过100000。

Output  
每组数据输出一行，如果该城堡符合小鑫的想法，那么输出”Yes”，否则输出”No”。

Example Input  
5  
2 5  
2 3  
1 3  
3 6  
4 6  
6  
1 2  
1 3  
3 4  
3 5  
5 6  
6 4

Example Output  
Yes  
No

Hint

Author  
xj

以下为accepted代码

#include <stdio.h>
    #include <string.h>
    #define INF 0x3f3f3f3f
    int f[100004], vis[100004];
    void init(int n)///初始化
    {
        for(int i = 1; i <= n; i++)
        {
            f[i] = i;
        }
    }
    int getf(int v)//寻找根结点
    {
        while(v != f[v])
        {
            v = f[v];
        }
        return v;
    }
    void merge(int u, int v)//元素的区间合并
    {
        int t1 = getf(u);
        int t2 = getf(v);
        if(t1 != t2)
            f[t2] = t1;
    }
    int main()
    {
        int m, u, v, i, max, min, flag, count;
        while(scanf("%d", &m) != EOF)
        {
            max = -1, min = INF;//初始化（min和max寻找所有房间标号的最小号和最大号）
            flag = count = 0;//标记变量和计数变量初始化
            memset(vis, 0 , sizeof(vis));//标记数组初始化
            init(100004);///并查集记录数组初始化
            for(i = 0; i < m; i++)
            {
                scanf("%d %d", &u, &v);
                if(min > u)//寻找最小值
                    min = u;
                if(min > v)//寻找最小值
                    min = v;
                if(max < u)//寻找最大值
                    max = u;
                if(max < v)//寻找最大值
                    max = v;
                int t1 = getf(u);//寻找根结点
                int t2 = getf(v);//寻找根结点
                if(t1 == t2)//判断根结点是否相同
                    flag = 1;
                else
                    merge(u, v);//元素的区间合并
                vis[u] = 1, vis[v] = 1;
            }
            if(flag)
                printf("No\n");
            else
            {
                for(i = min; i <= max; i++)//查询根结点个数
                {
                    if(vis[i] == 1 && f[i] == i)
                        count++;
                }
                if(count == 1)
                    printf("Yes\n");
                else
                    printf("No\n");
            }
        }
        return 0;
    }
    /*需要判断的情况：1是否有多个根结点，2是否有回路存在*/
    
    
    /***************************************************
    User name: 
    Result: Accepted
    Take time: 40ms
    Take Memory: 888KB
    Submit time: 2017-02-20 21:50:30
    ****************************************************/

[sdut]: http://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Contest/contestproblem/cid/2014/pid/2798