sol
cookiebus
2023-12-06 16:59:16
2023-12-06 17:13:32
8
返回题目
#include <bits/stdc++.h>
using namespace std;
vector<int> a[10001];
bool vis[10001];
int n, m, u, v;
void dfs(int u) {
vis[u] = true;
for (int i = 0; i < a[u].size(); ++i) {
int v = a[u][i];
if (!vis[v])
dfs(v);
}
}
int main() {
cin >> n >> m;
for (int i = 1; i <= m; ++i) {
cin >> u >> v;
a[u].push_back(v);
a[v].push_back(u);
}
int ans = 0;
for (int i = 1; i <= n; ++i) {
if (vis[i] == false) {
ans++;
dfs(i);
}
}
cout << ans << endl;
return 0;
}
#include <bits/stdc++.h>
using namespace std;
vector<int> a[10001];
bool vis[10001];
int n, m, u, v, en;
int h[10001]; // h[i] 表示 i 出发的第一条边的编号
struct Edge {
int u, v, nxt;
} e[400000];
void add(int u, int v) {
en++; // edge number
e[en].u = u;
e[en].v = v;
e[en].nxt = h[u];
h[u] = en;
}
void dfs(int u) {
vis[u] = true;
for (int i = h[u]; i > 0; i = e[i].nxt) {
int v = e[i].v;
if (!vis[v])
dfs(v);
}
}
int main() {
cin >> n >> m;
for (int i = 1; i <= m; ++i) {
cin >> u >> v;
add(u, v);
add(v, u);
}
int ans = 0;
for (int i = 1; i <= n; ++i) {
if (vis[i] == false) {
ans++;
dfs(i);
}
}
cout << ans << endl;
return 0;
}
{{ vote && vote.total.up }}