Pagini recente » Cod sursa (job #2662508) | Cod sursa (job #1678892) | Cod sursa (job #787978) | Cod sursa (job #3128582) | Cod sursa (job #1882859)
#include <cstdio>
#include <vector>
#include <queue>
#include <cstring>
#include <algorithm>
#define pb push_back
#define NMax 100010
using namespace std;
vector<int> G[NMax], Gt[NMax], ctc[NMax];
int N, M, nrsol, a, b, use[NMax], i, j, st[NMax];
inline void DFS (int nod)
{
use[nod]=1;
for(int i=0; i<G[nod].size(); i++)
if(!use[G[nod][i]]) DFS(G[nod][i]);
st[++st[0]]=nod;
}
inline void DFST (int nod)
{
use[nod]=1;
for(int i=0; i<Gt[nod].size(); i++)
if(!use[Gt[nod][i]]) DFST(Gt[nod][i]);
ctc[nrsol].pb(nod);
}
int main()
{
freopen("ctc.in","r",stdin);
freopen("ctc.out","w",stdout);
scanf("%d %d", &N, &M);
for(i=1; i<=M; i++)
{
scanf("%d %d", &a, &b);
G[a].pb(b);
Gt[b].pb(a);
}
for(i=1; i<=N; i++)
if(!use[i]) DFS(i);
memset(use, 0, sizeof(use));
for(i=N; i>=1; i--)
if(!use[st[i]])
{
++nrsol;
DFST(st[i]);
}
printf("%d\n", nrsol);
for(i=1; i<=nrsol; i++)
{
for(j=0; j<ctc[i].size(); j++)
printf("%d ", ctc[i][j]);
printf("\n");
}
return 0;
}