文章
9
粉丝
126
获赞
8
访问
24.3k
#include <bits/stdc++.h>
using namespace std;
vector<int> neibor[1000];//neibor[i]:结点i的邻居们
int visit[1000];//visit[i]:结点i是否被访问过
void dfs(int x) {
visit[x]=1;
for(int i=0;i<neibor[x].size();i++){
if(visit[neibor[x][i]]==0)
dfs(neibor[x][i]);
}
}
int main() {
int n,m,x,y;//n个点 m条路
while(cin>>n) {
if(n==0) break;
cin>>m;
//初始化参数
for(int i=0;i<n;i++){
neibor[i].clear();
visit[i]=0;
}
//建图
for(int i=0; i<m; i++) {
cin>>x>>y;
neibor[x-1].push_back(y-1);
neibor[y-1].push_back(x-1);
}
//dfs
int sum=0;
for(int i=0; i<n; i++) {
if(visit[i]==0) {
dfs(i);
sum++;
}
}
cout<<sum-1<<endl;
}
}
登录后发布评论
暂无评论,来抢沙发