Pagini recente » Cod sursa (job #1614598) | Cod sursa (job #468583) | Cod sursa (job #1205096) | Istoria paginii runda/oni_11_12_7 | Cod sursa (job #1251662)
#include <fstream>
#include <vector>
#define DMAX 100010
using namespace std;
ifstream fin ("ctc.in");
ofstream fout ("ctc.out");
vector <int> G[DMAX], GT[DMAX], sol[DMAX];
int uz[DMAX], postordine[DMAX];
int n, m, lg, comp;
void citire();
void DFSi(int);
void DFSt(int);
int main()
{
int i, j;
citire();
for (i=1; i<=n; ++i)
if (uz[i]==0)
DFSi(i);
for(i=1; i<=n; i++)
uz[i]=0;
for(i=n; i>=1; i--)
if(uz[postordine[i]]==0)
{
comp++;
DFSt(postordine[i]);
}
fout<<comp<<'\n';
for(i=1; i<=comp; i++)
{
for(j=0; j<sol[i].size(); j++)
fout<<sol[i][j]<<' ';
fout<<'\n';
}
return 0;
}
void citire()
{
int i, x, y;
fin>>n>>m;
for(i=1; i<=m; i++)
{
fin>>x>>y;
G[x].push_back(y);
GT[y].push_back(x);
}
}
void DFSi(int k)
{
int i;
uz[k]=1;
for (i=0; i<G[k].size(); i++)
if (uz[G[k][i]]==0)
DFSi(G[k][i]);
postordine[++lg]=k;
}
void DFSt(int k)
{
int i;
uz[k]=1;
sol[comp].push_back(k);
for (i=0; i<GT[k].size(); i++)
if (uz[GT[k][i]]==0)
DFSt(GT[k][i]);
}