文章
25
粉丝
0
获赞
74
访问
2.6k
#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;
}
登录后发布评论
暂无评论,来抢沙发