Cod sursa(job #2670536)

Utilizator tudosa.bogdanTudosa Eduard-Bogdan tudosa.bogdan Data 10 noiembrie 2020 09:42:35
Problema Sortare topologica Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.1 kb
#include <bits/stdc++.h>
#define IOS ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define NMAX 50005

using namespace std;

FILE *fin = fopen("sortaret.in" , "r");
FILE *fout = fopen("sortaret.out" , "w");

int n , m , interior[NMAX];

queue <int> Q;

vector <int> muchii[NMAX];
vector <int> ::iterator it;

map <pair <int , int> , int > arc;

int main()
{
    fscanf(fin , "%d%d" , &n , &m);
    for(int i = 1 ; i <= m ; i ++)
    {
        int x , y;
        fscanf(fin , "%d%d" , &x , &y);
        arc[make_pair(x , y)] ++;
        if(arc[make_pair(x , y)] == 1)
        {
            muchii[x].push_back(y);
            interior[y] ++;
        }
    }
    for(int i = 1 ; i <= n ; i ++)
        if(!interior[i])
            Q.push(i);
    while(!Q.empty())
    {
        int curent = Q.front();
        Q.pop();
        for(it = muchii[curent].begin() ; it != muchii[curent].end() ; it ++)
        {
            interior[*it] --;
            if(!interior[*it])
                Q.push(*it);
        }
        fprintf(fout , "%d " , curent);
    }
    return 0;
}