Pagini recente » Cod sursa (job #600976) | Cod sursa (job #3246586) | Cod sursa (job #410731) | Cod sursa (job #2749239) | Cod sursa (job #3227223)
#include <bits/stdc++.h>
using namespace std;
ifstream in("ctc.in");
ofstream out("ctc.out");
struct G {
vector<vector<int>> adj, radj;
int n, m;
};
G read_graph() {
G ret;
in >> ret.n >> ret.m;
ret.adj.resize(ret.n);
ret.radj.resize(ret.n);
for (int i = 0; i < ret.m; i++) {
int u, v;
in >> u >> v;
--u, --v;
ret.adj[u].push_back(v);
ret.radj[v].push_back(u);
}
return ret;
}
struct SCCS {
vector<vector<int>> comps;
vector<int> comp_map;
};
void topsort_from(G &g, int u, vector<char> &vis, vector<int> &order) {
stack<int> s;
s.push(u);
vis[u] = 1;
while (!s.empty()) {
int u = s.top();
for (int v : g.adj[u]) {
if (!vis[v]) {
vis[v] = 1;
s.push(v);
}
}
if (s.top() == u) {
s.pop();
order.push_back(u);
}
}
}
void discover_component(G &g, int u, SCCS &sccs) {
int comp_id = sccs.comps.size();
sccs.comps.push_back({});
stack<int> s;
s.push(u);
sccs.comp_map[u] = comp_id;
sccs.comps[comp_id].push_back(u);
while (!s.empty()) {
int u = s.top();
for (int v : g.radj[u]) {
if (sccs.comp_map[v] == -1) {
sccs.comp_map[v] = comp_id;
sccs.comps[comp_id].push_back(v);
s.push(v);
}
}
if (s.top() == u) {
s.pop();
}
}
}
SCCS find_sccs(G &g) {
vector<char> vis(g.n);
vector<int> order;
for (int i = 0; i < g.n; i++) {
if (!vis[i]) {
topsort_from(g, i, vis, order);
}
}
SCCS ret;
ret.comp_map.resize(g.n, -1);
for (int i = 0; i < g.n; ++i) {
if (ret.comp_map[i] != -1) {
continue;
}
discover_component(g, i, ret);
}
return ret;
}
int main() {
G g = read_graph();
SCCS sccs = find_sccs(g);
out << sccs.comps.size() << '\n';
for (auto &comp : sccs.comps) {
for (int u : comp) {
out << u + 1 << ' ';
}
out << '\n';
}
}