Pagini recente » Cod sursa (job #656572) | Cod sursa (job #2445121) | Cod sursa (job #57091) | Cod sursa (job #2069013) | Cod sursa (job #637746)
Cod sursa(job #637746)
#include <cstdio>
#include <vector>
#include <cstring>
using namespace std;
#define file_in "ctc.in"
#define file_out "ctc.out"
#define nmax 101000
int N,M;
int a,b,i,ans,j;
int ord[nmax];
int viz[nmax];
vector<int> G[nmax];
vector<int> sol[nmax];
void dfs(int nod){
if (viz[nod])
return ;
viz[nod]=1;
vector<int> :: iterator it;
ord[++ord[0]]=nod;
for (it=G[nod].begin();it!=G[nod].end();++it)
if (!viz[*it])
dfs(*it);
}
void dfst(int nod){
if (viz[nod])
return ;
viz[nod]=1;
vector<int> :: iterator it;
sol[ans].push_back(nod);
for (it=G[nod].begin();it!=G[nod].end();++it)
if (!viz[*it])
dfst(*it);
}
int main(){
freopen(file_in,"r",stdin);
freopen(file_out,"w",stdout);
scanf("%d %d", &N, &M);
while(M--){
scanf("%d %d", &a, &b);
G[a].push_back(b);
}
for (i=1;i<=N;++i)
if (!viz[i])
dfs(i);
memset(viz,0,sizeof(viz));
ans=0;
for (i=ord[0];i>=1;--i)
if (!viz[i]){
ans++;
dfst(i);
}
printf("%d\n", ans);
for (i=1;i<=ans;++i){
for (j=0;j<sol[i].size();++j)
printf("%d ", sol[i][j]);
printf("\n");
}
return 0;
}