Pagini recente » Cod sursa (job #1623051) | Cod sursa (job #2125140) | Cod sursa (job #1239980) | Cod sursa (job #1391348) | Cod sursa (job #2766929)
#include <iostream>
#include <fstream>
#include <list>
#include <stack>
#include <vector>
#include <string>
std::ifstream fin("ctc.in");
std::ofstream fout("ctc.out");
std::list<int> adj[100001];
std::list<int> adj2[100001];
std::vector<std::vector<int>> result;
std::vector<int> aux;
int nr_comp = 0;
void dfs2(int source, bool *visited) {
aux.push_back(source);
visited[source] = true;
for (auto &it:adj2[source]) {
if (!visited[it]) {
dfs2(it, visited);
}
}
}
void dfs(int source, bool *visited, std::stack<int>& stack) {
visited[source] = true;
for (auto &it: adj[source]) {
if (!visited[it]) {
dfs(it, visited, stack);
}
}
stack.push(source);
}
int main(void) {
// read inputs
int n, m, nr_comp = 0;
fin >> n >> m;
for (int i = 1; i <= m; ++i) {
int x, y;
fin >> x >> y;
adj[x].push_back(y);
// transpose graph
adj2[y].push_back(x);
}
// k algorithm
std::stack<int> stack;
bool visited[n];
for (int i = 1; i <= n; ++i) {
visited[i] = false;
}
for (int i = 1; i <= n; ++i) {
if (visited[i] == false) {
dfs(i, visited, stack);
}
}
for (int i = 1; i <= n; ++i) {
visited[i] = false;
}
while (!stack.empty()) {
int top = stack.top();
stack.pop();
if (visited[top] == false) {
aux.clear();
nr_comp++;
dfs2(top, visited);
result.push_back(aux);
}
}
fout << nr_comp << "\n";
for (auto it:result) {
for (auto it2:it) {
fout << it2 << " ";
}
fout << "\n";
}
fin.close();
fout.close();
return 0;
}