Pagini recente » Cod sursa (job #2854010) | Profil nouseforaname | Istoria paginii runda/test_clasa9/clasament | Cod sursa (job #2266964) | Cod sursa (job #693798)
Cod sursa(job #693798)
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<bitset>
#include<vector>
#define infile "ctc.in"
#define outfile "ctc.out"
#define n_max 100005
#define pb push_back
#define nxt *it
#define FOR(g) \
for(vector<int> :: iterator it = g.begin(); it!=g.end(); ++it)
using namespace std;
vector < int > v[n_max], vt[n_max];
vector < int > post, sol[n_max];
bitset < n_max > viz;
int N, M, Nsol;
void citeste()
{
freopen(infile,"r",stdin);
scanf("%d %d", &N, &M);
int x,y;
while(M--)
{
scanf("%d %d",&x,&y);
v[x].pb(y);
vt[y].pb(x);
}
fclose(stdin);
}
void DFS(int x)
{
viz[x] = 1;
FOR(v[x])
if(!viz[nxt])
DFS(nxt);
post.pb(x);
}
void DFST(int x)
{
viz[x] = 0;
FOR(vt[x])
if(viz[nxt])
DFST(nxt);
sol[Nsol].pb(x);
}
void rezolva()
{
for(int i=1; i<=N; ++i)
if(!viz[i])
DFS(i);
reverse(post.begin(), post.end());
FOR(post)
if(viz[nxt]){
Nsol++;
DFST(nxt);
}
}
void afiseaza()
{
freopen(outfile,"w",stdout);
printf("%d\n",Nsol);
for(int i=1; i<=Nsol; ++i){
FOR(sol[i])
printf("%d ",nxt);
printf("\n");
}
fclose(stdout);
}
int main()
{
citeste();
rezolva();
afiseaza();
return 0;
}