Pagini recente » Cod sursa (job #144045) | Cod sursa (job #1875946) | Cod sursa (job #3162046) | Cod sursa (job #1570492) | Cod sursa (job #2432458)
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <iostream>
#include <string.h>
#include <vector>
void dfs(int src, std::vector<bool> &visited, std::vector<int> *adj) {
visited[src] = true;
for (int i = 0 ; i < adj[src].size() ; ++i) {
if (!visited[adj[src][i]]) {
visited[adj[src][i]] = true;
dfs(adj[src][i], visited, adj);
}
}
}
int main() {
int N, M, src, dest;
freopen("dfs.in", "r", stdin);
freopen("dfs.out", "w", stdout);
scanf("%d%d", &N, &M);
assert(1 <= N && N <= 100000);
assert(0 <= M && M <= std::min(N * (N + 1) / 2, 200000));
std::vector<int> *adj = new std::vector<int>[N + 1];
std::vector<bool> visited(N + 1, false);
for (; M; --M) {
scanf("%d %d", &src, &dest);
adj[src].push_back(dest);
}
int counter = 0;
for (int i = 1 ; i <= N ; ++i) {
if (!visited[i]) {
++counter;
dfs(i, visited, adj);
}
}
printf("%d\n", counter);
delete [] adj;
return 0;
}