Pagini recente » Cod sursa (job #673523) | Cod sursa (job #2553509) | Cod sursa (job #1810486) | Cod sursa (job #2656131) | Cod sursa (job #3164086)
#include <iostream>
#include <vector>
#include <list>
#include <fstream>
//std::ifstream fin("doc/dfs.in");
//std::ofstream fout("doc/dfs.out");
const int NMAX = 1000000;
std::vector<std::list<int>> L;
int vis[NMAX];
void making_lists(int m) {
// Making the ajacengy list
for (int i = 0; i < m; i++) {
int x, y;
std::cin >> x >> y;
L[x - 1].push_front(y);
}
}
void dfs(int x) {
//std::cout << x << " ";
vis[x] = 1;
std::list<int>::iterator j = L[x].begin();
while (j != L[x].end()) {
if (!vis[*j - 1]) {
dfs(*j - 1);
}
j++;
}
}
int main (int argc, char *argv[]) {
// Test if the file has succesfully open
/*
if (!fin.is_open()) {
std::cout << "Error: Failed to open file." << std::endl;
exit(1);
}
*/
int n, m, numb = 0;
// Reading graph data
std::cin >> n; // Number of nodes
std::cin >> m; // Number of vertices
L.resize(n);
making_lists(m);
for (int i = 0; i < n; i++) {
if (vis[i] == 0) {
numb++;
dfs(i);
}
}
std::cout << numb << std::endl;
//fin.close();
//fout.close();
return 0;
}