Pagini recente » Clasament master_1 | Cod sursa (job #3203089) | Diferente pentru implica-te/extinde-arhiva/acord intre reviziile 20 si 13 | Cod sursa (job #2078090) | Cod sursa (job #1580933)
//Problem kosaraju
#include <cassert>
#include <cmath>
#include <cstdint>
#include <algorithm>
#include <fstream>
#include <iostream>
#include <string>
#include <vector>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
#define cin fin
#define cout fout
#define pb push_back
typedef vector<vector<int>> VVI;
int N, M;
VVI graph;
VVI sccs;
void dfs(int node, VVI &graph, vector<bool> &vis, vector<int> &st) {
vis[node] = 1;
for (auto v: graph[node]) {
if (!vis[v]) dfs(v, graph, vis, st);
}
st.push_back(node);
}
void kosaraju() {
vector<int> ts;
vector<bool> vis(N + 1, 0);
for (int i = 1; i <= N; i += 1) {
if (!vis[i]) dfs(i, graph, vis, ts);
}
fill(vis.begin(), vis.end(), 0);
reverse(ts.begin(), ts.end());
while (!ts.empty()) {
int node = ts.back();
ts.pop_back();
if (vis[node]) continue;
sccs.push_back(vector<int>());
dfs(node, graph, vis, sccs.back());
}
}
void readin() {
cin >> N >> M;
graph.resize(N + 1);
for (int i = 1, a, b; i <= M; i += 1) {
cin >> a >> b;
graph[a].pb(b);
}
}
void printout() {
cout << sccs.size() << endl;
for (auto c: sccs) {
for (auto v: c) {
cout << v << ' ';
}
cout << '\n';
}
}
int main() {
readin();
kosaraju();
printout();
return 0;
}