并查集-HDU 1232-畅通工程

绝地灬酷狼 2022-05-15 01:56 201阅读 0赞

*  # 并查集-HDU 1232-畅通工程 #

--------------------

*  ## 题目链接：[畅通工程][Link 1] ##
 *  ## 并查集基础： ##

### [数据结构-并查集][-] ###

*  ## 思路： ##

### 题目大意： ###

中文自己看题

### 题解： ###

**两个城市都可以实现交通：从一个城市可以通过公路到达另一个城市，不一定要直达**

很容易想，实现交通只要N个城市连成一条线就ok，也就是**最少公路数为：MAX\_Road\_Num=N-1**

给了M条直达公路，问最少还要修几条，两种情况

**a.该直达公路连着的两个城市原本就连通，那这条直达公路相当于白修**

**b.两个城市只通过该直达公路连接，有效公路，MAX\_Road\_Num-1，并且把这两个城市并入一个集合表示互通**

*  ## 代码： ##

#include<iostream>
    using namespace std;
    #define MAX_SIZE 1024
    int Node[MAX_SIZE];
    
    void Init(int n)
    {
        for(int i=0;i<=n;i++)
            Node[i]=-1;
    }
    
    int Find(int City)
    {
        if(Node[City]==-1)
            return City;
        else
            return Find(Node[City]);
    }
    
    int Combine(int a,int b)
    {
        int a_root=Find(a);
        int b_root=Find(b);
        //cout<<a_root<<" "<<b_root<<endl;
        if(a_root!=b_root)   //该公路使原本交通不便的两个城市互通
        {
            Node[a_root]=b_root;   //a 所在集合加入b
            return 1;
        }
        else
            return 0;
    }
    
    int main()
    {
        int N,M;
        while(cin>>N&&N)
        {
            cin>>M;
            Init(N);
    
            int Road_Num=N-1;
            while(M--)
            {
                int a,b;
                cin>>a>>b;
                Road_Num-=Combine(a,b);
            }
            cout<<Road_Num<<endl;
        }
        return 0;
    }

[Link 1]: http://acm.hdu.edu.cn/showproblem.php?pid=1232
[-]: https://blog.csdn.net/SZU_Crayon/article/details/81986258