Pagini recente » Cod sursa (job #2241627) | Cod sursa (job #2177370) | Cod sursa (job #435409) | Cod sursa (job #2405343) | Cod sursa (job #1251342)
#include <fstream>
#include <vector>
#define dmax 100005
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int n, m, ct, poz_postord, uz[dmax],postord[dmax];
vector <int> grf[dmax];
vector <int> grft[dmax];
vector <int> sol[dmax];
void citire();
void rezolvare();
void dfs1(int );
void dfs2(int );
void afisare();
int main(){
citire();
rezolvare();
afisare();
return 0;
}
void citire(){
int x, y;
fin>>n>>m;
for(int i=1; i<=m; ++i)
{
fin>>x>>y;
grf[x].push_back(y);
grft[y].push_back(x);
}
}
void rezolvare(){
int i;
for(i=1; i<=n; i++)
if(!uz[i])
dfs1(i);
for(i=1; i<=n; ++i) uz[i]=0;
for(i=n; i>0; --i)
if(!uz[postord[i]]){
ct++;
dfs2(postord[i]);
}
}
void dfs1(int vf){
uz[vf]=1;
for(int i=0; i<grf[vf].size(); ++i)
if(!uz[grf[vf][i]])
dfs1(grf[vf][i]);
postord[++poz_postord]=vf;
}
void dfs2(int vf){
sol[ct].push_back(vf);
uz[vf]=1;
for(int i=0; i<grft[vf].size(); ++i)
if(!uz[grft[vf][i]])
dfs2(grft[vf][i]);
}
void afisare(){
int i, j;
fout<<ct<<'\n';
for(i=1; i<=ct; ++i){
for(j=0; j<sol[i].size(); ++j)
fout<<sol[i][j]<<" ";
fout<<'\n';
}
}