Cod sursa(job #2969655)

Utilizator HAUBAUHAULICA TUDOR HAUBAU Data 23 ianuarie 2023 15:41:09
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.91 kb
#include <iostream>
#include <vector>
#include <stack>
#include <bits/stdc++.h>
using namespace std;
ifstream fin("sortaret.in");
ofstream fout("sortaret.out");

const int MAXN = 200001;
vector<int> graph[MAXN];
bool visited[MAXN];
int n, m;
int gr[MAXN]; // gr[i] = gradul interior al lui i


void citire()
{    memset(gr, 0, MAXN*sizeof(int));
    fin>>n>>m;
    int x,y;
    for(int i = 0 ; i < m ; i++ )
    {   fin>>x>>y;
        graph[x].push_back(y);
        gr[y]++;
    }

}

void topsort()
{
    queue<int> q;
    for(int i = 1 ; i <= n ; i++ )
        if(gr[i] == 0)
            q.push(i);

    while(!q.empty())
    {   int x = q.front();
        q.pop();
        fout<<x<<" ";
        for(int i = 0 ; i < graph[x].size() ; i++ )
        {   gr[graph[x][i]]--;
            if(gr[graph[x][i]] == 0)
                q.push(graph[x][i]);
        }
    }

}


int main() {
    citire();
    topsort();

    return 0;
}