Pagini recente » Cod sursa (job #843799) | Cod sursa (job #648461) | Cod sursa (job #2584111) | Cod sursa (job #152963) | Cod sursa (job #499475)
Cod sursa(job #499475)
#include<fstream>
#include<vector>
using namespace std;
#define Nmax 100001
vector<int> G[Nmax],Gt[Nmax],Comp[Nmax];
int n,m,nrc,postordine[Nmax],nr, k,vizitat[Nmax];
void citire()
{
int i,x,y;
ifstream f("ctc.in");
f>>n>>m;
for(i=1;i<=m;i++)
{
f>>x>>y;
G[x].push_back(y);
Gt[y].push_back(x);
}
f.close();
}
void df(int nod)
{
int i,vecini;
vizitat[nod]=1;
vecini=G[nod].size();
for(i=0; i < vecini; i++)
if (!vizitat[G[nod][i]])
df(G[nod][i]);
postordine[++nr]=nod;
}
void df2(int nod)
{
int i,vecini;
Comp[nrc].push_back(nod);
vizitat[nod]=0;
vecini= Gt[nod].size();
for(i=0;i<vecini;i++)
if (vizitat[Gt[nod][i]])
df2(Gt[nod][i]);
}
int main()
{
int i,vecini,j;
citire();
for(i=1;i<=n;i++)
if (!vizitat[i])
df(i);
for(i=n;i>0;i--)
if (vizitat[postordine[i]])
{
nrc++;
k=0;
df2(postordine[i]);
}
ofstream g("ctc.out");
g<<nrc<<"\n";
for(i=1;i<=nrc;i++)
{
vecini=Comp[i].size();
for(j=0;j<vecini;j++)
g<<Comp[i][j]<<" ";
g<<"\n";
}
g.close();
return 0;
}