Pagini recente » Cod sursa (job #2676841) | Cod sursa (job #2945107) | pregoni2011 | Cod sursa (job #1282438) | Cod sursa (job #2072420)
#include <cstdio>
#include <vector>
#define MAXN (int)1e5
int N, M;
std::vector <int> v[MAXN + 1], inv[MAXN + 1];
bool viz[MAXN + 1];
std::vector <int> sol;
void topodfs(int nod) {
if(viz[nod])
return;
viz[nod] = 1;
for(auto x : v[nod]) {
topodfs(x);
}
sol.push_back(nod);
}
std::vector <int> ans[MAXN + 1];
int cnt;
void dfs(int nod) {
if(!viz[nod])
return;
viz[nod] = 0;
for(auto &x : inv[nod]) {
dfs(x);
}
ans[cnt].push_back(nod);
}
int main() {
freopen("ctc.in", "r", stdin);
freopen("ctc.out", "w", stdout);
scanf("%d%d", &N, &M);
for(int i = 1;i <= M;i++) {
int x, y;
scanf("%d%d", &x, &y);
v[x].push_back(y);
inv[y].push_back(x);
}
for(int i = 1;i <= N;i++)
topodfs(i);
for(int i = sol.size() - 1;i >= 0;i--) {
if(viz[sol[i]]) {
dfs(sol[i]);
cnt++;
}
}
printf("%d\n", cnt);
for(int i = 0;i < cnt;i++) {
for(auto x : ans[i])
printf("%d ", x);
printf("\n");
}
return 0;
}//Pai ce ma m-am tampit?