Pagini recente » Cod sursa (job #365291) | Cod sursa (job #2680721) | Cod sursa (job #3275709) | Cod sursa (job #3169674) | Cod sursa (job #500517)
Cod sursa(job #500517)
#include <vector>
#include <stdio.h>
#include <string.h>
#define pb push_back
using namespace std;
vector <int> L[100010], LT[100010];
bool sel[100010];
int st[100010], i, n, m, x, y, nr=0, nrc=0;
void dfs1(int x){
vector <int>::iterator it;
sel[x]=true;
for (it=L[x].begin();it!=L[x].end();it++)
if (!sel[*it]) dfs1(*it);
st[++nr]=x;
}
void dfs2(int x, bool ok){
vector <int>::iterator it;
sel[x]=true;
if (ok) printf("%d ",x);
for (it=LT[x].begin();it!=LT[x].end();it++)
if (!sel[*it]) dfs2(*it, ok);
}
void load(){
scanf("%d %d\n", &n, &m);
for (i=1; i<= m; i++){
scanf("%d %d\n",&x, &y);
L[x].pb(y);
LT[y].pb(x);
}
return;
}
int main(){
freopen("ctc.in","r",stdin);
freopen("ctc.out","w",stdout);
load();
memset(sel, false, sizeof(sel));
for (i=1; i<=n; i++)
if (!sel[i])
dfs1(i);
memset(sel, false, sizeof(sel));
for (i=n; i>=1; i--)
if (!sel[st[i]]){
nrc++;
dfs2(st[i],false);
}
printf("%d\n", nrc);
memset(sel, false, sizeof(sel));
for (i=n; i>=1; i--)
if (!sel[st[i]]){
dfs2(st[i],true);
printf("\n");
}
return 0;
}