题解 | #畅通工程#

#include<iostream>

const int MAX = 1000;

class UnionFind
{
    private:
    int m_Father[MAX];
    int m_Height[MAX];
    int m_cnt=0;
    public:
    UnionFind(int n)
    {
        for(int i=1;i <=n;i++)
        {
            m_Father[i] = i;
            m_Height[i] = 0;
        }
    }

    int Find(int x)
    {
        if(x != m_Father[x])
        {
            m_Father[x] = Find(m_Father[x]);
        }
        return m_Father[x];
    }

    void Union(int x, int y)
    {
        int x_father = Find(x);
        int y_father = Find(y);
        if(x_father != y_father)
        {
            if(m_Height[x_father] < m_Height[y_father])
                m_Father[x_father] = y_father;
            else if(m_Height[x_father] > m_Height[y_father])
                m_Father[y_father] = x_father;
            else
            {
                m_Father[y_father] = x_father;
                m_Height[x_father]++;
            }
        }
    }
    int Count(int n)
    {
        for(int i=1;i<=n;i++)
        {
            if(i == Find(i))
                m_cnt++;
        }
        return m_cnt-1;
    }

};

int main()
{
    int townNum, roadNum;
    int roadA, roadB;
    while (std::cin >> townNum)
    {
        if(townNum == 0) break;
        std::cin >> roadNum;
        UnionFind* uf = new UnionFind(townNum);
        for(int i=0;i<roadNum;i++)
        {
            std::cin >> roadA >> roadB;
            uf->Union(roadA, roadB);
        }
        std::cout << uf->Count(townNum) << std::endl;
	  delete uf;
    }
    
}