题解 | #畅通工程#

#include<iostream>
//通过深度优先遍历统计连通分量的个数，从而得出还需要修建的最少道路
const int MAX = 1000;

class DFS_Count
{
    private:
    int cnt, n;
    int Graph[MAX][MAX];
    bool visited[MAX];
    public:
    DFS_Count(int N): n(N), cnt(0)//初始化邻接矩阵表示的图和标记数组是否被访问过的visited数组
    {
        for(int i=0; i<MAX; i++)
        {
            for(int j=0; j<MAX; j++)
            {
                Graph[i][j] = 0;
            }
        }
        for(int i=0; i<MAX; i++)
        {
            visited[i] = false;
        }
    }

    void setGraph(const int& a, const int& b)
    {
        Graph[a-1][b-1] = 1;
        Graph[b-1][a-1] = 1;
    }

    void DFS(const int& v)//递归进行深度优先遍历
    {
        visited[v] = true;
        for(int i=0;i<n;i++)
        {
            if(Graph[i][v] && !visited[i])//找到与v相邻且没有被访问过的节点
                DFS(i);
        }
    }

    int Count()
    {
        for(int i=0;i<n;i++)
        {
            if(!visited[i])//统计连通分量的个数
            {
                cnt++;
                DFS(i);
            }
        }
        return cnt-1;
    }
};

int main()
{
    int n, m, a, b;
    while (std::cin >> n)
    {
        if(n == 0) break;
        std::cin >> m;
        DFS_Count* dfs = new DFS_Count(n);
        for(int i=0;i<m;i++)
        {
            std::cin >> a >> b;
            dfs->setGraph(a, b);
        }
        std::cout << dfs->Count() << std::endl;
        delete dfs;
    }
    
}