Pagini recente » Cod sursa (job #2785012) | Cod sursa (job #2494148) | Cod sursa (job #2874002) | Cod sursa (job #136809) | Cod sursa (job #897033)
Cod sursa(job #897033)
#include<stdio.h>
#include<vector>
#define maxn 100005
using namespace std;
FILE*f=fopen("ctc.in","r");
FILE*g=fopen("ctc.out","w");
int n,m,ctc;
int st[maxn],viz[maxn];
vector<int>G[maxn],Gt[maxn],C[maxn];
void dfp ( int nod ){
viz[nod] = 1;
for ( vector<int>::iterator itt = G[nod].begin() ; itt != G[nod].end() ; ++itt ){
int vecin = (*itt);
if ( !viz[vecin] ){
dfp(vecin);
}
}
st[++st[0]] = nod;
}
void dfm ( int nod ){
viz[nod] = 0; C[ctc].push_back(nod);
for ( vector<int>::iterator itt = Gt[nod].begin() ; itt != Gt[nod].end() ; ++itt ){
int vecin = (*itt);
if ( viz[vecin] ){
dfm(vecin);
}
}
}
int main () {
fscanf(f,"%d %d",&n,&m);
int x,y;
for ( int i = 1 ; i <= m ; ++i ){
fscanf(f,"%d %d",&x,&y);
G[x].push_back(y);
Gt[y].push_back(x);
}
for ( int i = 1 ; i <= n ; ++i ){
if ( !viz[i] ){
dfp(i);
}
}
for ( int i = n ; i >= 1 ; --i ){
if ( viz[st[i]] ){
++ctc;
dfm(st[i]);
}
}
fprintf(g,"%d\n",ctc);
for ( int i = 1 ; i <= ctc ; ++i ){
for ( int j = 0 ; j < C[i].size() ; ++j ){
fprintf(g,"%d ",C[i][j]);
}
fprintf(g,"\n");
}
fclose(f);
fclose(g);
return 0;
}