文章

25

粉丝

0

获赞

74

访问

2.6k

头像
图的连通分支数 用set很方便喵题解:
P1456 上海交通大学机试题
发布于2026年2月15日 11:03
阅读数 125

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 9;
int fa[N];
bool vis[N];

int find(int x)
{
	if(x == fa[x]) return x;
	else{
		return fa[x] = find(fa[x]);
	}
}

void merge(int x, int y)
{
	int nx = find(x); int ny = find(y);
	if(nx == ny) return;
	else {fa[nx] = ny; return;}
}
//上面两个就是并查集的模板嗷
int main()
{
	int x, y; 
	memset(fa, 0, sizeof(fa));
	memset(vis, 0, sizeof(vis));
	for(int i = 1; i <= 1e5; i ++) fa[i] = i;
	while(cin >> x >> y)
	{
		merge(x, y);
		vis[x] = true; vis[y] = true;
	}
	set<int> st; int cnt = 0;
	for(int i = 1; i <= 1e5; i ++){
		if(vis[i]){
			if(!st.count(find(i))){cnt ++; st.insert(find(i));}
		}
	}
	
	cout << cnt;
}

 

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发