文章

150

粉丝

0

获赞

522

访问

22.2k

头像
图的连通分支数 题解:
P1456 上海交通大学机试题
发布于2026年3月2日 13:52
阅读数 108

#include<bits/stdc++.h>
using namespace std;

vector<int> g[1010];//定义邻接表:g[i]存储节点i的所有邻居节点
bool vis[1000];//访问标记数组:vis[i]=true表示节点i已被DFS遍历过
void dfs(int x){
	vis[x]=true;
	for(int y:g[x]){ //遍历x的所有邻居y
		if(!vis[y])
			dfs(y);
	}
}

int main(){
	set<int> st;//哈希集合st,用于收集所有出现过的节点(自动去重)
	int i,j;
	while(cin>>i>>j){//读入边信息
		st.insert(i);
		st.insert(j);//将两个端点加入集合(记录有哪些节点)
		g[i].push_back(j);
		g[j].push_back(i);//无向图:i和j互相加入对方的邻接表
	}
	int ans=0;
	for(int x:st){//遍历所有出现过的节点
		if(!vis[x]){//如果节点x未被访问,说明发现了一个新的连通分量
			ans++;
			dfs(x);
		}
	}
	cout<<ans<<endl;

return 0;
}

 

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发