Pagini recente » Cod sursa (job #2003750) | Istoria paginii runda/new | Cod sursa (job #1710574) | Istoria paginii runda/minue5/clasament | Cod sursa (job #2665464)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("sortaret.in");
ofstream fout("sortaret.out");
bool vizitat[100005]; //un vector de muchii vizitate
vector<int> listaMuchii[100005], nou_sortat; //vector pentru lista de muchii
//folosim algoritmul de dfs doar ca la final mai adaugam intr-un vector
//toate elementele pe care le intalnim in parcurgerea in adancime dintr-un nod dat
//pentru a fi sortate topologic
void dfs(int nod)
{
int vecin;
vizitat[nod] = true;
for (int i = 0; i < listaMuchii[nod].size(); i++)
{
vecin = listaMuchii[nod][i];
if (!vizitat[vecin])
dfs(vecin);
}
nou_sortat.push_back(nod);
}
//ne folosim de dfs pt a parcurge si sorta topologic graful dat
int main()
{
int noduri, muchii, i, x, y;
//citim nodurile si muchiile pe care le bagam intr-o lista de adiacenta
fin >> noduri >> muchii;
for (i = 0; i < muchii; i++)
{
fin >> x >> y;
listaMuchii[x].push_back(y);
}
//parcurgem fiecare nod si daca acesta nu a mai fost vizitat folosim dfs incepand din el
for (i = 1; i <= noduri; i++)
if (!vizitat[i])
{
dfs(i);
}
//afisam vectorul de sortare topologica
for (i = nou_sortat.size() - 1; i >= 0; i--)
{
fout << nou_sortat[i] << " ";
}
return 0;
}