Pagini recente » Cod sursa (job #1825446) | Cod sursa (job #494519) | Cod sursa (job #2172620) | Cod sursa (job #3218682) | Cod sursa (job #2100926)
#include <vector>
#include <list>
#include <fstream>
#include <iostream>
class GraphHelper {
public:
static void reversePostorder(int k, const std::vector<std::list<int>>& edges, std::vector<bool>& marked, std::list<int>& out) {
if (marked[k])
return;
marked[k] = true;
for (int x : edges[k])
reversePostorder(x, edges, marked, out);
out.push_front(k);
}
static void preorder(int k, const std::vector<std::list<int>>& edges, std::vector<bool>& marked, std::list<int>& out) {
if (marked[k])
return;
marked[k] = true;
out.push_back(k);
for (int x : edges[k])
preorder(x, edges, marked, out);
}
};
class DGraph {
public:
DGraph(int _n) : n(_n), edge(_n), redge(_n) {}
void add_edge(int u, int v) {
edge[u].push_back(v);
redge[v].push_back(u);
}
void kosaraju(std::list<std::list<int>>& out) {
std::list<int> rpos;
{
std::vector<bool> marked(n, false);
for (int i = 0; i < n; i++) {
if (marked[i])
continue;
GraphHelper::reversePostorder(i, redge, marked, rpos);
}
}
{
std::vector<bool> marked(n, false);
for (int x : rpos) {
if (marked[x])
continue;
out.push_back(std::list<int>());
GraphHelper::preorder(x, edge, marked, out.back());
}
}
}
private:
int n;
std::vector<std::list<int>> edge;
std::vector<std::list<int>> redge;
};
int main() {
std::ifstream in("ctc.in");
int n, m;
in >> n >> m;
DGraph g(n);
for (int i = 0; i < m; i++) {
int u, v;
in >> u >> v;
g.add_edge(u - 1, v - 1);
}
std::list<std::list<int>> components;
g.kosaraju(components);
std::ofstream out("ctc.out");
out << components.size() << "\n";
for (const auto& comp : components) {
for (int x : comp)
out << x + 1 << " ";
out << "\n";
}
return 0;
}