Pagini recente » Sandbox (cutiuţa cu năsip) | Cod sursa (job #1624213) | Cod sursa (job #1338314) | Cod sursa (job #2327152) | Cod sursa (job #1841658)
#include <algorithm>
#include <fstream>
#include <vector>
using namespace std;
using Graph = vector<vector<int>>;
using Component = vector<int>;
Graph Reverse(const Graph &g)
{
Graph rev(g.size());
for (unsigned i = 0; i < g.size(); ++i)
for (int node : g[i])
rev[node].push_back(i);
return rev;
}
void DFS(const Graph &g, int node, vector<bool> &vis, vector<int> &ord)
{
vis[node] = true;
for (int n : g[node])
if (!vis[n])
DFS(g, n, vis, ord);
ord.push_back(node);
}
vector<int> TopoSort(const Graph &g)
{
vector<bool> visited(g.size(), false);
vector<int> order;
for (unsigned i = 0; i < g.size(); ++i)
if (!visited[i])
DFS(g, i, visited, order);
reverse(order.begin(), order.end());
return order;
}
Component ExtractComponent(const Graph &g, int node, vector<bool> &used)
{
Component comp;
DFS(g, node, used, comp);
return comp;
}
vector<Component> SCC(const Graph &g)
{
auto rev = Reverse(g);
auto order = TopoSort(rev);
vector<Component> comp;
vector<bool> used(g.size(), false);
for (unsigned i = 0; i < g.size(); ++i) {
int node = order[i];
if (!used[node])
comp.push_back(ExtractComponent(g, node, used));
}
return comp;
}
int main()
{
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int n, m;
fin >> n >> m;
Graph graph(n);
while (m--) {
int x, y;
fin >> x >> y;
graph[x - 1].push_back(y - 1);
}
auto comp = SCC(graph);
fout << comp.size() << "\n";
for (auto c : comp) {
for (auto node : c)
fout << node + 1 << " ";
fout << "\n";
}
return 0;
}