Pagini recente » Cod sursa (job #764544) | Cod sursa (job #1060818) | Cod sursa (job #1350131) | Cod sursa (job #1690945) | Cod sursa (job #476931)
Cod sursa(job #476931)
using namespace std;
#include<iostream>
#include<fstream>
#include<vector>
#define Nmax 100005
#define pb push_back
#define foreach(v) for(typeof (v).begin() it=(v).begin();it!=(v).end();it++)
vector<int> G[Nmax];
vector<int> TG[Nmax];
vector<int> ans[Nmax];
//vector<int>::iterator it;
ofstream fout("ctc.out");
int N,M,nr=0,postord[Nmax],viz[Nmax];
void DFS(int u)
{ viz[u]=1;
foreach(G[u])
if(viz[*it]==0)
{ //cout<<*it<<" ";
DFS(*it);
}
postord[++nr]=u;
}
void DFS2(int u)
{
viz[u]=0;
foreach(TG[u])
if(viz[*it])
DFS2(*it);
ans[nr].pb(u);
}
void solve()
{
int i,j;
for(i=1;i<=N;i++)
if(!viz[i])
{DFS(i);
}
nr=0;
for(i=N;i>=1;i--)
if(viz[postord[i]])
{nr++;
DFS2(postord[i]);
}
fout<<nr<<"\n";
for(i=1;i<=nr;i++)
{
for(j=0;j<ans[i].size();j++)
fout<<ans[i][j]<<" ";
fout<<"\n";
}
}
void cit()
{int i,x,y;
ifstream fin("ctc.in");
fin>>N>>M;
for(i=1;i<=M;i++)
{ fin>>x>>y;
G[x].pb(y);
TG[y].pb(x);
}
fin.close();
}
int main()
{
cit();
solve();
fout.close();
return 0;
}