题解 | DFS+visited[i]数组

#include <iostream>
#include <fstream>
#include <vector>


using namespace std;

void dfs(const vector<vector<bool>>& matrix,int x,vector<bool>& visited );

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    //ifstream fin("C:\\Users\\Administrator\\Desktop\\Code\\c2006b\\fin.txt");
    //ofstream fout("C:\\Users\\Administrator\\Desktop\\Code\\c2006b\\fout.txt");
    int n,m,x,y,counter;
    while(cin>>n>>m)
    {
        if(n==0)
            break;
        counter=0;
        vector<vector<bool>> matrix(n,vector<bool>(n,false));
        vector<bool> visited(n,false);
        for(int i=0;i<m;++i)
        {
            cin>>x>>y;
            matrix[x-1][y-1]=matrix[y-1][x-1]=true;
        }
        for(int i=0;i<n;++i)
        {
            if(visited[i]==false)
            {
                dfs(matrix,i,visited);
                ++counter;
            }
        }
        cout<<counter-1<<endl;

    }

//    int m,n;
//    while(fin>>m>>n)
//    {
//        for(int i=1;i<=n-2;++i)
//        {
//            for(int j=i+1;j<=n-1;++j)
//            {
//                for(int k=j+1;k<=n;++k)
//                {
//                    fout<<i<<" "<<j<<" "<<k<<endl;
//                }
//            }
//        }
//    }
    return 0;
}

void dfs(const vector<vector<bool>>& matrix,int x,vector<bool>& visited )
{
    int nsize=matrix.size();
    visited[x]=true;
    for(int i=0;i<nsize;++i)
    {
        if(matrix[x][i]==true&&visited[i]==false)
        {
            dfs(matrix,i,visited);
        }
    }
}