Cod sursa(job #2832407)

Utilizator ciobyCiobanu Vlasie cioby Data 13 ianuarie 2022 17:15:25
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.85 kb
#include <fstream>
#include <iostream>
using namespace std;
ifstream fin("sortaret.in");
ofstream fout("sortaret.out");

int lmax = 0;
int n, m;

typedef struct graf {
	int x;
	graf* a;

}*pnod;

pnod g[100001];
int f[100001];
int stiva[100001];
int vf = 0;

void legatura(pnod &dest, int val)
{
	pnod p = new graf;
	p->x = val;
	p->a = dest;
	dest = p;
}

void citire()
{
	fin >> n >> m;
	for (int i = 1; i <= m; i++)
	{
		int x, y;
		fin >> x >> y;
		legatura(g[x], y);
	}
}

void dfs(int nod)
{
	f[nod] = 1;
	for (pnod p = g[nod]; p != NULL; p = p->a)
	{
		if (!f[p->x])
		{
			dfs(p->x);
		}
	}
	stiva[++vf] = nod;
}

void rezolvare()
{
	for (int i = 1; i <= n; i++)
	{
		if (f[i] == 0) dfs(i);
	}
	for (int i = vf; i >= 1; i--)
		fout << stiva[i] << ' ';
}

int main()
{
	citire();
	rezolvare();
}