题解 | #畅通工程#

#include <iostream>
using namespace std;
const int N=1002;
int n,m,a,b;
int cont;
int G[N][N];
bool visited[N]={false};
void Initial(){
    cont=0;
    for(int i=1;i<=1000;i++){
        for(int j=1;j<=1000;j++)
           G[i][j]=G[j][i]=0;
    }
    for(int i=1;i<=1000;i++) visited[i]=false;
}
void DFS(int v){
    visited[v]=true; //置已访问标记
    for(int u=1;u<=n;u++){
        //即如果u顶点是v顶点的邻接顶点，且u顶点尚未访问过
        if(G[v][u]==1 && visited[u]==false) DFS(u);
    }
}
void DFSTraverse(){
   for(int i=1;i<=n;i++){
      //计算连通分量数
      if(visited[i]==false){
         cont++;
         DFS(i);
      } 
   }
}
int main() {
   while(cin>>n>>m){
      Initial();
      for(int i=0;i<m;i++){
         cin>>a>>b;
         G[a][b]=G[b][a]=1;
      }
      DFSTraverse();
      cout<<cont-1<<endl;
   }
   return 0;
}