Pagini recente » Cod sursa (job #1103934) | Cod sursa (job #871088) | Cod sursa (job #2060968) | Cod sursa (job #1596893) | Cod sursa (job #3356920)
#include <iostream>
#include <fstream>
using namespace std;
int n, m, x, y;
int head[100005];
int to[200005];
int nxt[200005];
int edge_cnt;
int dfn[100005];
int low[100005];
int timer;
int st[100005];
int vf;
int in_st[100005];
int ans[100005];
int ans_start[100005];
int ans_end[100005];
int nr_comp;
int ans_sz;
void adauga_muchie(int u, int v) {
edge_cnt++;
to[edge_cnt] = v;
nxt[edge_cnt] = head[u];
head[u] = edge_cnt;
}
void dfs(int nod) {
timer++;
dfn[nod] = timer;
low[nod] = timer;
vf++;
st[vf] = nod;
in_st[nod] = 1;
for (int i = head[nod]; i != 0; i = nxt[i]) {
int vecin = to[i];
if (dfn[vecin] == 0) {
dfs(vecin);
if (low[vecin] < low[nod]) {
low[nod] = low[vecin];
}
} else if (in_st[vecin] == 1) {
if (dfn[vecin] < low[nod]) {
low[nod] = dfn[vecin];
}
}
}
if (low[nod] == dfn[nod]) {
nr_comp++;
ans_start[nr_comp] = ans_sz + 1;
while (st[vf] != nod) {
int curent = st[vf];
vf--;
in_st[curent] = 0;
ans_sz++;
ans[ans_sz] = curent;
}
int curent = st[vf];
vf--;
in_st[curent] = 0;
ans_sz++;
ans[ans_sz] = curent;
ans_end[nr_comp] = ans_sz;
}
}
int main() {
ifstream fin("ctc.in");
ofstream fout("ctc.out");
fin >> n >> m;
for (int i = 1; i <= m; i++) {
fin >> x >> y;
adauga_muchie(x, y);
}
for (int i = 1; i <= n; i++) {
if (dfn[i] == 0) {
dfs(i);
}
}
fout << nr_comp << "\n";
for (int i = 1; i <= nr_comp; i++) {
for (int j = ans_start[i]; j <= ans_end[i]; j++) {
fout << ans[j] << " ";
}
fout << "\n";
}
return 0;
}