Pagini recente » Cod sursa (job #293778) | Cod sursa (job #1419684) | Cod sursa (job #1637854) | Cod sursa (job #1811417) | Cod sursa (job #1266345)
#include <iostream>
#include <stdio.h>
#include <vector>
using namespace std;
vector <int> nodes [100001];
int visited [100001];
void solve(int node) {
int noNeighbors = nodes[node].size();
for (int i = 0; i < noNeighbors; ++ i) {
if (visited[nodes[node][i]] == 0) {
visited[nodes[node][i]] = 1;
solve(visited[nodes[node][i]]);
}
}
}
int main(int argc, const char * argv[]) {
int n, m;
int connectedCount = 0;
freopen("dfs.in", "r", stdin);
freopen("dfs.out", "w", stdout);
scanf("%d", &n);
scanf("%d", &m);
for (int i = 0; i < m; ++ i) {
int node, neighbor;
scanf("%d%d", &node, &neighbor);
nodes[node].push_back(neighbor);
}
for (int i = 1; i <= n; ++ i) {
if (visited[i] == 0) {
++ connectedCount;
visited[i] = 1;
solve(i);
}
}
printf("%d\n", connectedCount);
return 0;
}