Pagini recente » Cod sursa (job #2652565) | Cod sursa (job #18960) | Cod sursa (job #1147132) | Cod sursa (job #3231164) | Cod sursa (job #2928907)
#include<fstream>
#include<vector>
#define MaxN 200005
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
vector<int>G[MaxN],Gt[MaxN],sol[MaxN];
int post[MaxN],viz[MaxN],n,m,k,nr;
void dfs(int i)
{ vector<int>::iterator it;
viz[i]=1;
for(it=G[i].begin();it!=G[i].end();++it)
if(!viz[*it])
dfs(*it);
post[++nr]=i;
}
void dfsm(int i)
{ vector<int>::iterator it;
viz[i]=0;
sol[k].push_back(i);
for(it=Gt[i].begin();it!=Gt[i].end();++it)
if(viz[*it])
dfsm(*it);
}
int main()
{ int i,x,y;
fin>>n>>m;
for(i=1;i<=m;i++)
{ fin>>x>>y;
G[x].push_back(y);
Gt[y].push_back(x);
}
for(i=1;i<=n;i++)
if(!viz[i])
dfs(i);
for(i=n;i>0;i--)
if(viz[post[i]])
{ k++;
dfsm(post[i]);
}
fout<<k<<'\n';
vector<int>::iterator it;
for(i=1;i<=k;i++)
{ for(it=sol[i].begin();it!=sol[i].end();it++)
fout<<*it<<' ';
fout<<'\n';
}
return 0;
}