Pagini recente » Cod sursa (job #1102206) | Cod sursa (job #234444) | Cod sursa (job #1999895) | Cod sursa (job #1006280) | Cod sursa (job #596445)
Cod sursa(job #596445)
#include<fstream>
#include<cstdlib>
using namespace std;
int n,m;
int *A[1000],np[1000];
int postordine[1000],nr;
bool vizitat[1000];
//np[i] = numarul predecesorilor sai care nu au fost inca plasati pe niveluri
//adica gradul interior in subgraful curent
void Citire()
{
int i,x,y;
ifstream fin("sortaret.in");
fin>>n>>m;
for(i=1;i<=n;i++)
{
A[i]=(int *)realloc(A[i],sizeof(int));
A[i][0]=0;
}
for(i=1;i<=m;i++)
{
fin>>x>>y;
//construiesc graful
A[x][0]++;
A[x]=(int *)realloc(A[x],(A[x][0]+1)*sizeof(int));
A[x][A[x][0]]=y;
np[y]++;
}
fin.close();
}
void DFS(int x)
{
int i;
vizitat[x]=true;
for(i=1;i<=A[x][0];i++)
{
if(vizitat[A[x][i]]==false)
DFS(A[x][i]);
}
postordine[++nr]=x; //numerotez nodurile grafului in postordine
//nodul x este numerotat dupa ce toti succesorii sai au fost numerotati
}
int main()
{
int i;
Citire();
ofstream fout("sortaret.out");
//parcurgem graful DFS determinand ordinea nodurilor
for(i=1;i<=n;i++)
{
if(vizitat[i]==false)
DFS(i);
}
for(i=n;i>0;i--)
fout<<postordine[i]<<' ';
fout<<"\n";
fout.close();
return 0;
}