Pagini recente » Cod sursa (job #935437) | Cod sursa (job #1846667) | Cod sursa (job #459295) | Cod sursa (job #2869092) | Cod sursa (job #2126628)
#include <bits/stdc++.h>
using namespace std;
struct Kosaraju {
int n, ccs;
vector<vector<int>> G, T, R;
vector<int> stk, vis, comp;
Kosaraju(int n) : n(n), G(n), T(n), vis(n), comp(n) {}
void AddEdge(int a, int b) {
G[a].push_back(b);
T[b].push_back(a);
}
void dfs1(int node) {
vis[node] = 1;
for (auto vec : G[node])
if (vis[vec] == 0)
dfs1(vec);
stk.push_back(node);
}
void dfs2(int node, int cc) {
vis[node] = 2;
comp[node] = cc;
for (auto vec : T[node])
if (vis[vec] == 1)
dfs2(vec, cc);
}
vector<int> Solve() {
for (int node = 0; node < n; ++node) {
if (vis[node] == 0)
dfs1(node);
}
reverse(stk.begin(), stk.end());
for (auto node : stk) {
if (vis[node] == 1)
dfs2(node, ccs++);
}
return comp;
}
vector<vector<int>> BuildCondensation() {
Solve();
vector<vector<int>> R(ccs);
for (int node = 0; node < n; ++node) {
for (auto vec : G[node]) {
if (comp[vec] != comp[node]) {
R[comp[node]].push_back(comp[vec]);
}
}
}
for (int i = 0; i < ccs; ++i) {
sort(R[i].begin(), R[i].end());
R[i].erase(unique(R[i].begin(), R[i].end()), R[i].end());
}
return R;
}
};
struct Mine {
int pos, rad, cost;
bool operator<(const Mine& oth) const {
return pos < oth.pos;
}
};
int main() {
ifstream cin("ctc.in");
ofstream cout("ctc.out");
int n, m; cin >> n >> m;
Kosaraju ctc(n);
for (int i = 0; i < m; ++i) {
int a, b; cin >> a >> b;
ctc.AddEdge(a - 1, b - 1);
}
auto comp = ctc.Solve();
vector<vector<int>> nodes(n + 1);
int ccs = 0;
for (int i = 0; i < n; ++i) {
nodes[comp[i]].push_back(i);
ccs = max(ccs, comp[i] + 1);
}
cout << ccs << endl;
for (int i = 0; i < ccs; ++i) {
for (auto x : nodes[i])
cout << x + 1 << " ";
cout << endl;
}
return 0;
}