Pagini recente » Cod sursa (job #1951347) | Istoria paginii preoni-2006/runda-4/clasament-10 | Cod sursa (job #2028955) | Cod sursa (job #2216790) | Cod sursa (job #1517142)
#include <fstream>
#include <vector>
#include <cstring>
using namespace std;
FILE *f=freopen("ctc.in","r",stdin);
FILE *g=freopen("ctc.out","w",stdout);
vector <int> G[100001],GT[100001],S[100001],o;
int n,m,viz[100001],sol;
void read();
void DFS(int);
void DFST(int);
void solve();
void write();
int main(){
read();
solve();
write();
}
void read(){
scanf("%d%d",&n,&m);
for (int i=1;i<=m;i++){
int x,y;
scanf("%d%d",&x,&y);
G[x].push_back(y);
GT[y].push_back(x);
}
}
void solve(){
for (int i=1;i<=n;i++){
if (!viz[i]){
DFS(i);
}
}
memset(viz,0,sizeof(viz));
for (int i=o.size()-1;i>=0;i--){
if (!viz[o[i]]){
sol++;
DFST(o[i]);
}
}
}
void DFS(int x){
viz[x]=1;
for (int i=0;i<G[x].size();i++){
int y=G[x][i];
if (!viz[y]){
DFS(y);
}
}
o.push_back(x);
}
void DFST(int x){
viz[x]=1;
S[sol].push_back(x);
for (int i=0;i<GT[x].size();i++){
int y=GT[x][i];
if (!viz[y]){
DFST(y);
}
}
}
void write(){
printf("%d\n",sol);
for (int i=1;i<=sol;++i){
for (int j=0;j<S[i].size();j++){
printf("%d ",S[i][j]);
}
printf("\n");
}
}