Pagini recente » Cod sursa (job #2140014) | Arhiva de probleme | Cod sursa (job #1400743) | Cod sursa (job #1307766) | Cod sursa (job #1108314)
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
#define MAXN 100001
int N, M;
vector<int> g[MAXN], gr[MAXN];
vector<vector<int>> components;
int seen[MAXN];
vector<int> top_sorted;
inline void init_seen() {
memset(seen, 0, MAXN * sizeof(int));
}
void read() {
scanf("%d%d", &N, &M);
for(int i = 0; i < M; ++i) {
int x, y;
scanf("%d%d", &x, &y);
g[x].push_back(y);
gr[y].push_back(x);
}
}
void write() {
printf("%zu\n", components.size());
for(const vector<int>& c : components) {
for(int x : c) {
printf("%d ", x);
}
printf("\n");
}
}
void dfs(int u) {
seen[u] = 1;
for(int v : g[u])
if(!seen[v])
dfs(v);
top_sorted.push_back(u);
}
void forward() {
for(int u = 1; u <= N; ++u)
if(!seen[u])
dfs(u);
}
void dfsr(int u) {
seen[u] = 1;
components.back().push_back(u);
for(int v : gr[u])
if(!seen[v])
dfsr(v);
}
void backwards() {
for(auto rit = top_sorted.rbegin(); rit != top_sorted.rend(); ++rit) {
if(!seen[*rit]) {
components.push_back(vector<int>());
dfsr(*rit);
}
}
}
void kosaraju() {
init_seen();
forward();
init_seen();
backwards();
}
int main(int argc, char *argv[]) {
freopen("ctc.in", "r", stdin);
freopen("ctc.out", "w", stdout);
read();
kosaraju();
write();
return 0;
}