Pagini recente » Cod sursa (job #1201598) | Cod sursa (job #2356830) | Cod sursa (job #2927195) | Cod sursa (job #1586218) | Cod sursa (job #3222700)
#include <iostream>
#include <fstream>
#include <vector>
#include <list>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
vector<list<int>> graph, transGraph;
list<int> finished;
vector<bool> visitedGraph, visitedTransGraph;
list<list<int>> ctc;
int total = 0;
void dfsGraph(int node)
{
for(auto& node_ : graph[node])
{
if(!visitedGraph[node_])
{
visitedGraph[node_] = true;
dfsGraph(node_);
}
}
finished.push_back(node);
}
void dfsTransGraph(int node)
{
(*prev(ctc.end())).push_back(node);
for(auto& node_ : transGraph[node])
{
if(!visitedTransGraph[node_])
{
visitedTransGraph[node_] = true;
dfsTransGraph(node_);
}
}
}
int main()
{
int n, m;
fin >> n >> m;
graph.resize(n + 1);
transGraph.resize(n + 1);
visitedGraph = vector<bool>(n + 1, false);
visitedTransGraph = vector<bool>(n + 1, false);
for(int i = 0; i < m; i++)
{
int l, r;
fin >> l >> r;
graph[l].push_back(r);
transGraph[r].push_back(l);
}
for(int node = 1; node <= n; node++)
{
if(visitedGraph[node])
continue;
visitedGraph[node] = true;
dfsGraph(node);
}
for(auto it = finished.rbegin(); it != finished.rend(); it++)
{
if(visitedTransGraph[*it])
continue;
ctc.push_back(list<int>());
visitedTransGraph[*it] = true;
dfsTransGraph(*it);
total++;
}
fout << total << '\n';
for(auto& e : ctc)
{
for(auto& node : e)
{
fout << node << ' ';
}
fout << '\n';
}
return 0;
}