Pagini recente » Cod sursa (job #1534625) | Cod sursa (job #1818200) | Cod sursa (job #922136) | Cod sursa (job #248265) | Cod sursa (job #2948071)
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int n, m;
vector <int> graph[200005];
vector <int> transposedGraph[200005];
bool visited[200005];
vector <int> topSort;
vector <int> ans;
vector <vector <int>> allAns;
void TopDFS(int node) {
visited[node] = true;
for (int newNode : graph[node]) {
if (visited[newNode]) {
continue;
}
TopDFS(newNode);
}
topSort.push_back(node);
}
void ReconstructionDFS(int node) {
visited[node] = true;
for (int newNode : transposedGraph[node]) {
if (visited[newNode]) {
continue;
}
ReconstructionDFS(newNode);
}
ans.push_back(node);
}
void GenerateTransposedGraph() {
for (int i = 1; i <= n; i++) {
for (int node : graph[i]) {
transposedGraph[node].push_back(i);
}
}
}
int main() {
fin >> n >> m;
for (int i = 0; i < m; i ++) {
int a, b;
fin >> a >> b;
graph[a].push_back(b);
}
for (int i = 1; i <= n; i++) {
if (visited[i]) {
continue;
}
TopDFS(i);
}
// Topological Sort vec
reverse(topSort.begin(), topSort.end());
// Reset visited
for (int i = 1; i <= n; i++) {
visited[i] = false;
}
// Generate transposed
GenerateTransposedGraph();
// DFS
for (int node : topSort) {
if (visited[node]) {
continue;
}
ReconstructionDFS(node);
allAns.push_back(ans);
// Reset local answer
ans.clear();
}
// Answer
fout << allAns.size() << '\n';
for (auto vec : allAns) {
for (auto node : vec) {
fout << node << ' ';
}
fout << '\n';
}
}