算法1
借助并查集,找无环连通块的个数
C++ 代码
#include<iostream>
#include<string>
#include<cstring>
#include<algorithm>
#include<set>
using namespace std;
typedef long long ll;
#define int long long
#define endl '\n'
const int N = 100005;
int n, m;
int p[N];
bool st[N];//st[i]表示祖宗顶点为i的连通块是否有环
int ans = 0;
int find(int x) {
if (x != p[x])return p[x] = find(p[x]);
return p[x];
}
// 找无环连通块的个数
void solve()
{
cin >> n >> m;
for (int i = 1; i <= n; i++)p[i] = i;
while (m--) {
int x, y;
cin >> x >> y;
// 找各自的祖宗
x = find(x), y = find(y);
if (x == y) {// 存在环
st[x] = true;
}
else {// 都认y做祖宗
p[x] = y; st[y] |= st[x];
}
}
for (int i = 1; i <= n; i++) {
if (p[i] == i && !st[i]) {
ans++;
}
}
cout << ans << endl;
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int t = 1;
//cin >> t;
while (t--) {
solve();
}
return 0;
}