Cod sursa(job #2668341)

Utilizator BulaceanuAlexandraBulaceanu Alexandra-Irina BulaceanuAlexandra Data 4 noiembrie 2020 19:53:01
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.94 kb
#include <bits/stdc++.h>
#include <fstream>

using namespace std;

ifstream fin("sortaret.in");
ofstream fout("sortaret.out");

vector<int> muchii[100010];
bool vizitat[100010];
int grad[100010];
vector<int> sol;
queue <int> q;

void topologic()
{
    while(!q.empty())
    {
        int elem = q.front();
        q.pop();

        for (auto vecin : muchii[elem])
        {
            grad[vecin] --;
            if(grad[vecin] == 0 && !vizitat[vecin])
            {
                vizitat[vecin] = true;
                sol.push_back(vecin);
                q.push(vecin);
            }
        }
    }

}



int main() {
	int n, m, x, y;
	fin >> n >> m;

	for (int i = 1; i <= m; i++) {
		fin >> x >> y;
		muchii[x].push_back(y);
		grad[y]++;
	}

	for (int i = 1;i <= n;i++) {
		if (grad[i] == 0) sol.push_back(i), q.push(i);
	}

	topologic();

	for (int elem : sol)
	{
		fout << elem << " ";
	}
}