Pagini recente » Cod sursa (job #718285) | Cod sursa (job #833994) | Cod sursa (job #1129482) | Cod sursa (job #1803533) | Cod sursa (job #991220)
Cod sursa(job #991220)
#include <algorithm>
#include <fstream>
#include <iostream>
#include <vector>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
const int MAX_N = 100100;
int N, M;
vector<int> graph[MAX_N];
vector<int> transpose_graph[MAX_N];
vector<vector<int>> sccs;
void read_input();
void kosaraju();
void dfs(int node, vector<int> g[], vector<bool>& visited, vector<int>& st);
void print_output();
int main() {
read_input();
kosaraju();
print_output();
return 0;
}
void read_input() {
fin >> N >> M;
for (int i = 1, a, b; i <= M; ++i) {
fin >> a >> b;
graph[a].push_back(b);
transpose_graph[b].push_back(a);
}
}
void kosaraju() {
vector<int> sorted_nodes;
vector<bool> visited(N + 1, 0);
for (int i = 1; i <= N; ++i) {
if (!visited[i]) dfs(i, graph, visited, sorted_nodes);
}
fill(visited.begin(), visited.end(), 0);
while (!sorted_nodes.empty()) {
int node = sorted_nodes.back();
sorted_nodes.pop_back();
if (visited[node]) continue;
sccs.push_back(vector<int>());
dfs(node, transpose_graph, visited, sccs.back());
}
}
void dfs(int node, vector<int> g[], vector<bool>& visited, vector<int>& st) {
visited[node] = true;
for (auto x : g[node]) {
if (!visited[x]) dfs(x, g, visited, st);
}
st.push_back(node);
}
void print_output() {
fout << sccs.size() << '\n';
for (auto scc : sccs) {
for (auto node : scc) {
fout << node << ' ';
}
fout << '\n';
}
}