文章

9

粉丝

126

获赞

8

访问

24.5k

头像
连通分量个数-->dfs
P1319 浙江大学机试题
发布于2023年3月17日 15:28
阅读数 2.1k

#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;

	}


}

 

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发