Cod sursa(job #3261633)

Utilizator darian4444Verniceanu Darian darian4444 Data 7 decembrie 2024 09:24:51
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.71 kb
#include <bits/stdc++.h>
#define ll long long
using namespace std;

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

int N,M,x,y,i,j,v[50005];
vector<int> A[50005];
map< pair<int,int>, bool> seen;
deque<int> sorted;

void dfs(int k){
    v[k] = 1;

    for (auto next_n : A[k])
        if (!v[next_n])
            dfs(next_n);

    sorted.push_back(k);
}

int main()
{
    fin >> N >> M;

    for (i = 1;i <= M;i++){
        fin >> x >> y;
        if (!seen[{y,x}]);
        A[y].push_back(x);
        seen[{y,x}] = 1;
    }

    for (i = 1;i <= N;i++)
        if (!v[i])
            dfs(i);

    for (auto elem : sorted)
        fout << elem << " ";

    return 0;
}