Pagini recente » Cod sursa (job #2474224) | Cod sursa (job #2726725) | Cod sursa (job #1702661) | Cod sursa (job #2311867) | Cod sursa (job #1251029)
#include <cstdio>
#include <vector>
#define DMAX 100005
using namespace std;
FILE*fin=fopen("ctc.in","r");
FILE*fout=fopen("ctc.out","w");
vector <int> G[DMAX];
vector <int> T[DMAX];
vector <int> sol[DMAX];
int n, m, nrctc, pozpo;
int uz[DMAX];
int postord[DMAX];
void citire();
void rezolvare();
void DFSG(int vf);
void DFST(int vf);
void afisare();
int main(){
citire();
rezolvare();
afisare();
return 0;
}
void citire(){
int x, y;
fscanf(fin, "%d%d", &n, &m);
for(int i=1; i<=m; ++i){
fscanf(fin, "%d%d", &x, &y);
G[x].push_back(y);
T[y].push_back(x);
}
}
void rezolvare(){
int i;
for(i=1; i<=n; i++)
if(!uz[i])
DFSG(i);
for(i=1; i<=n; ++i) uz[i]=0;
for(i=n; i>0; --i)
if(!uz[postord[i]]){
nrctc++;
DFST(postord[i]);
}
}
void DFSG(int vf){
uz[vf]=1;
for(int i=0; i<G[vf].size(); ++i)
if(!uz[G[vf][i]])
DFSG(G[vf][i]);
postord[++pozpo]=vf;
}
void DFST(int vf){
sol[nrctc].push_back(vf);
uz[vf]=1;
for(int i=0; i<T[vf].size(); ++i)
if(!uz[T[vf][i]])
DFST(T[vf][i]);
}
void afisare(){
int i, j;
fprintf(fout, "%d\n", nrctc);
for(i=1; i<=nrctc; ++i){
for(j=0; j<sol[i].size(); ++j)
fprintf(fout, "%d ", sol[i][j]);
fprintf(fout, "\n");
}
fclose(fout);
}