CodeForces原题
E. New Reform
题意
求 非环的连通分量的个数
一、dfs
#include<bits/stdc++.h>
using namespace std;
//#define int long long
const int maxl = 1e6 + 7;
int n, m, ans;
vector<int> G[maxl];
bool vis[maxl];
bool dfs(int u, int fa) {
vis[u] = 1;
for (int v : G[u]) {
if (v == fa) continue;
if (vis[v] || dfs(v, u)) return true;
}
return false;
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> n >> m;
for (int i = 1, u, v; i <= m; i++) {
cin >> u >> v;
G[u].push_back(v);
G[v].push_back(u);
}
for (int i = 1; i <= n; i++) {
if (!vis[i] && !dfs(i, -1)) ans++;
}
cout << ans << endl;
return 0;
}
二、并查集
#include<bits/stdc++.h>
using namespace std;
//#define int long long
const int maxl = 1e6 + 7;
int n, m, ans;
int fa[maxl];
bool vis[maxl];
int find(int u) {
if (u != fa[u]) fa[u] = find(fa[u]);
return fa[u];
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> n >> m;
for (int i = 1; i <= n; i++) fa[i] = i;
for (int i = 1, a, b; i <= m; i++) {
cin >> a >> b;
int u = find(fa[a]), v = find(fa[b]);
if (u != v) {
vis[u] |= vis[v];
fa[v] = u;
} else vis[u] = 1;
}
for (int i = 1; i <= n; i++) if (i == find(i) && !vis[i]) ans++;
cout << ans << endl;
return 0;
}