Pagini recente » Cod sursa (job #199565) | Cod sursa (job #2246346) | Cod sursa (job #2556844) | Cod sursa (job #1537247) | Cod sursa (job #549262)
Cod sursa(job #549262)
#include <cstdio>
#include <vector>
using namespace std;
#define file_in "ctc.in"
#define file_out "ctc.out"
#define nmax 101000
int n,m,a,b,i,viz[nmax],j;
vector<int> G[nmax];
vector<int> Gt[nmax];
vector<int> sol[nmax];
int ord[nmax];
int nr;
void dfs(int nod){
if (viz[nod])
return ;
viz[nod]=1;
vector<int> :: iterator it;
for (it=G[nod].begin();it!=G[nod].end();++it)
if (!viz[*it])
dfs(*it);
ord[++ord[0]]=nod;
}
void dfst(int nod){
if (viz[nod])
return ;
viz[nod]=1;
sol[nr].push_back(nod);
vector<int> :: iterator it;
for (it=Gt[nod].begin();it!=Gt[nod].end();++it)
if (!viz[*it])
dfst(*it);
//ord[++ord[0]]=nod;
}
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);
Gt[b].push_back(a);
}
ord[0]=0;
memset(viz,0,sizeof(viz));
for (i=1;i<=n;++i)
if (!viz[i])
dfs(i);
memset(viz,0,sizeof(viz));
nr=0;
for (i=n;i>=1;--i)
if (!viz[ord[i]]){
nr++;
dfst(ord[i]);
}
printf("%d\n", nr);
for (i=1;i<=nr;++i){
for (j=0;j<sol[i].size();++j){
int xx=sol[i][j];
printf("%d ", xx);
}
printf("\n");
}
return 0;
}