Pagini recente » Cod sursa (job #2868984) | Cod sursa (job #2737849) | Cod sursa (job #2920906) | Cod sursa (job #2450985) | Cod sursa (job #752655)
Cod sursa(job #752655)
#include <cstdio>
#include <vector>
#define pb push_back
#include <cstring>
using namespace std;
vector<int> G[100010],GT[100010];
int nc, nr, i, k, N, M, x, y, St[100010];
bool sel[100010];
void DF(int x){
int i;
sel[x]=true;
for(i = 0; i < G[x].size(); ++i)
if (!sel[G[x][i]]) DF(G[x][i]);
St[++nr]=x;
}
void DFT(int x, bool k){
int i;
sel[x]=true;
if (k) printf("%d ", x);
for(i = 0; i < GT[x].size(); ++i)
if (!sel[GT[x][i]]) DFT(GT[x][i], k);
}
int main(){
freopen("ctc.in","r", stdin);
freopen("ctc.out","w",stdout);
scanf("%d %d\n", &N, &M);
for (i=1; i<=M; ++i){
scanf("%d %d\n", &x, &y);
G[x].pb(y);
GT[y].pb(x);
}
nr=0; nc=0;
memset(sel, false,sizeof(sel));
for(i=1; i<=N; i++)
if (!sel[i]) DF(i);
memset(sel, false,sizeof(sel));
for(i=N; i>0; --i)
if (!sel[St[i]])
{
DFT(St[i], false);
nc++;
}
printf("%d\n", nc);
memset(sel, false,sizeof(sel));
for(i=N; i>0; --i)
if (!sel[St[i]])
{
DFT(St[i], true);
printf("\n");
}
return 0;
}