Pagini recente » Cod sursa (job #2586849) | Cod sursa (job #1697578) | Cod sursa (job #2694454) | Cod sursa (job #289126) | Cod sursa (job #2704366)
#include <bits/stdc++.h>
using namespace std;
int dfs_1(const int root,
const vector<vector<int>>& g,
vector<pair<int, int>>& f) {
f[root].second = 0;
int adj_time = 0;
for (const int adj : g[root]) {
if (f[adj].second == -1) {
adj_time = max(adj_time, dfs_1(adj, g, f));
}
}
f[root].second = adj_time + 1;
return f[root].second;
}
void dfs_2(const int root,
const vector<vector<int>>& g,
vector<int>& sccs,
const int curr_scc) {
sccs[root] = curr_scc;
for (const int adj : g[root]) {
if (sccs[adj] == -1) {
dfs_2(adj, g, sccs, curr_scc);
}
}
}
vector<int> compute_sccs(const int n, const vector<vector<int>>& g) {
vector<pair<int, int>> f(n + 1);
for (int i = 1; i <= n; ++i) {
f[i] = make_pair(i, -1);
}
for (int i = 1; i <= n; ++i) {
if (f[i].second == -1) {
dfs_1(i, g, f);
}
}
vector<vector<int>> gt(n + 1);
for (int i = 1; i <= n; ++i) {
for (const int adj : g[i]) {
gt[adj].push_back(i);
}
}
auto cmp = [](const pair<int, int>& x, const pair<int, int>& y) {
return x.second > y.second;
};
sort(f.begin(), f.end(), cmp);
vector<int> sccs(n + 1, -1);
int next_scc = 1;
for (const pair<int, int>& p : f) {
if (p.first > 1 && sccs[p.first] == -1) {
dfs_2(p.first, gt, sccs, next_scc);
++next_scc;
}
}
return sccs;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
ifstream in("ctc.in", fstream::in);
in.tie(nullptr);
ofstream out("ctc.out", fstream::out);
out.tie(nullptr);
int n, m;
in >> n >> m;
vector<vector<int>> g(n + 1);
for (int i = 0; i < m; ++i) {
int u, v;
in >> u >> v;
g[u].push_back(v);
}
vector<int> sccs = compute_sccs(n, g);
unordered_map<int, vector<int>> scc_to_node;
for (int i = 1; i <= n; ++i) {
scc_to_node[sccs[i]].push_back(i);
}
out << scc_to_node.size() << "\n";
for (auto map_it = scc_to_node.begin(); map_it != scc_to_node.end();
++map_it) {
for (const int node : map_it->second) {
out << node << " ";
}
out << "\n";
}
}