看了好多人根本没用并查集,他来了
首先说明一下为什么是在连通块内找环,一个连通块内,有一个环,就可以形成首尾相连,环内没有孤立的点,再看如果有一个点与环相连,直接将这条边的方向改为环指向这个环外的点,结束
如何判断连通块内有没有环呢?
第一步,分连通块,用并查集
第二步,判断环,由于这题没有重边,所以 点数 = 边数 + 1 则没有环,反之有环
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
typedef long long LL;
int p[N], n, m, a, b, sum[N];
int find(int x){
if(x != p[x]){
p[x] = find(p[x]);
}
return p[x];
}
int main(){
cin >> n >> m;
for (int i = 1; i <= n; i ++){
p[i] = i;
}
for (int i = 1; i <= m; i ++){
cin >> a >> b;
sum[a] ++;
sum[b] ++;
p[find(a)] = find(b); // 并查集基础知识不讲了
}
map<int, pair<int, int>> ma;
for (int i = 1; i <= n; i ++){
ma[find(i)].first ++; //将点数都放到祖宗节点
ma[find(i)].second += sum[i]; // 将边数都放到祖宗节点
}
int ans = 0;
for (auto it : ma){
if(it.second.first - 1 == it.second.second/2){// 因为每个点存了一次边数,需要除以2
ans ++;
}
}
cout << ans << endl;
}