Pagini recente » Cod sursa (job #2865469) | Cod sursa (job #1687851) | Cod sursa (job #360139) | Cod sursa (job #2065871) | Cod sursa (job #3164089)
#include <iostream>
#include <vector>
#include <list>
#include <fstream>
std::ifstream fin("dfs.in");
std::ofstream fout("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;
fin >> 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
fin >> n; // Number of nodes
fin >> m; // Number of vertices
L.resize(n);
making_lists(m);
for (int i = 0; i < n; i++) {
if (vis[i] == 0) {
numb++;
dfs(i);
}
}
fout << numb;
fin.close();
fout.close();
return 0;
}