Pagini recente » Monitorul de evaluare | Cod sursa (job #1341421) | Cod sursa (job #1915053) | Cod sursa (job #1003338) | Cod sursa (job #252912)
Cod sursa(job #252912)
#include<stdio.h>
#define infile "sortaret.in"
#define outfile "sortaret.out"
#define nmax (50*1000+1)
#define mmax (100*1000+1)
struct lista
{
int n,p; //nod si pozitie
} l[mmax];
int p[nmax]; //pozitia din lista
int post[nmax]; //vectorul de psotordine al parcurgerii DFS
char viz[nmax]; //v[i]=1 daca a fost vizitat nodul i
int n; //numarul de noduri
//adauga arcul (x,y)
void add(struct lista l[mmax], int p[nmax], int m, int x, int y)
{
l[m].n=y; l[m].p=p[x]; p[x]=m;
}
void citire(struct lista l[mmax], int p[nmax], int *n)
{
int i,m,x,y;
scanf("%d %d\n",n,&m);
for(i=1;i<=m;i++)
{
scanf("%d %d\n",&x,&y); //citim arcul
add(l,p,i,x,y); //adaugam arcul in lista
}
}
void dfs(struct lista l[mmax], int p[nmax], int post[nmax], char viz[nmax], int n) //n - nodul din care facem parcurgerea
{
int ul=p[n];
while(ul) //cat timp n are copii
{
if(!viz[l[ul].n]) //daca fiul nu a fost vizitat
dfs(l,p,post,viz,l[ul].n); //parcurg fiul
ul=l[ul].p; //copilul urmator al lui n
}
post[++post[0]]=n; //marcam in vectorul de postordine ca am terminat de vizitat toti vecinii
}
int main()
{
int i;
freopen(infile,"r",stdin);
freopen(outfile,"w",stdout);
citire(l,p,&n); //citim datele din fisier si construim lista
for(i=1;i<=n;i++)
if(!viz[i]) //daca nodul nu a fost vizitat (vom avea o alta componenta conexa)
dfs(l,p,post,viz,i);
for(i=n;i>0;i--) //parcurgem si afisem vectorul de psotordine de la coada
printf("%d ",post[i]);
fclose(stdin);
fclose(stdout);
return 0;
}