Pagini recente » Cod sursa (job #481831) | Cod sursa (job #1982843) | Cod sursa (job #2227366) | Cod sursa (job #2149347) | Cod sursa (job #2842687)
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
ifstream in("in.in");
ofstream out("out.out");
#else
ifstream in("ctc.in");
ofstream out("ctc.out");
#endif
///this find the strongly connected components of directed
///graph g. It assumes the nodes in g are 1-indexed.
///the return value is a vector containing vectors representing
///the strongly connected components, by nodes.
vector<int> vis,tout;
int nr;
vector<int> List;
void dfs(int node, const vector<vector<int>> &g) {
vis[node] = 1;
for (auto k : g[node]) {
if (vis[k] == 0) {
vis[k] = 1;
dfs(k ,g);
}
}
tout[node] = ++nr;
List.push_back(node);
}
vector<int> component;
void dfs2(int node, const vector<vector<int>> &g) {
vis[node] = 1;
component.push_back(node);
for (auto k : g[node]) {
if (vis[k] == 0) {
vis[k] = 1;
dfs2(k ,g);
}
}
}
vector<vector<int>> scc(const vector<vector<int>> &g) {
int n = (int)g.size() - 1;
vector<vector<int>> revG(n + 1);
for (int i = 1; i <= n; i++) {
for (auto k : g[i]) {
revG[k].push_back(i);
}
}
nr = 0;
tout = vis = vector<int>(n + 1, 0);
for (int i = 1; i <= n; i++) {
if (vis[i] == 0) {
dfs(1, g);
}
}
vis = vector<int>(n + 1, 0);
nr = 0;
vector<vector<int>> res;
for (int i = List.size() - 1; i >= 0; i--) {
int node = List[i];
if (vis[node] == 0) {
nr++;
component.clear();
dfs2(node, revG);
res.push_back(component);
}
}
return res;
}
int main() {
int n,m;
in >> n >> m;
vector<vector<int>> g(n + 1);
for (int i = 1; i <= m; i++) {
int u,v;
in >> u >> v;
g[u].push_back(v);
}
vector<vector<int>> sol = scc(g);
out << sol.size() << "\n";
for (auto k : sol) {
for (auto node : k) {
out << node << " ";
}
out << "\n";
}
return 0;
}