Pagini recente » Cod sursa (job #403419) | Profil catalinaenachi | Rating Voicu Ionut (gion3) | Cod sursa (job #542079) | Cod sursa (job #2261719)
/* finding the number of connected components through a depth first search */
#include <bits/stdc++.h>
using namespace std;
const int NMAX = 123000;
int n, m;
vector<int> adj[NMAX];
bool visited[NMAX];
void dfs(int u) {
visited[u] = true;
for (int v : adj[u]) {
if (!visited[v]) {
dfs(v);
}
}
}
int main() {
ios_base::sync_with_stdio(false);
freopen("dfs.in", "r", stdin);
freopen("dfs.out", "w", stdout);
cin >> n >> m;
for (int i = 0; i < m; i++) {
int x, y;
cin >> x >> y;
adj[x].push_back(y);
}
for (int i = 0; i < NMAX; i++) {
visited[i] = false;
}
int ans = 0;
for (int i = 1; i <= n; i++) {
if (!visited[i]) {
dfs(i);
ans++;
}
}
cout << ans << endl;
return 0;
}