Cod sursa(job #2521830)

Utilizator richardbaczur1Baczur Richard richardbaczur1 Data 11 ianuarie 2020 16:14:20
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.06 kb
#include <bits/stdc++.h>
#define NMAX 50005
#define MMAX 100005
#define infile "sortaret.in"
#define outfile "sortaret.out"

using namespace std;

struct nod{
    vector<int> adj;
};

vector<nod> v;
int n, m, x, y, deg[NMAX];

void solve()
{
    queue<int> q;

    for (int i = 1; i <= n; i++)
    {
        if (!deg[i])
        {
            q.push(i);
        }
    }

    int nod;
    while (!q.empty())
    {
        nod = q.front();
        printf("%d ", nod);
        q.pop();
        for (int i = 0; i < v[nod].adj.size(); i++)
        {
            deg[v[nod].adj[i]]--;
            if (!deg[v[nod].adj[i]])
            {
                q.push(v[nod].adj[i]);
            }
        }
    }
}

int main()
{
    freopen(infile, "r", stdin);
    freopen(outfile, "w", stdout);

    scanf("%d %d", &n, &m);
    v.resize(n + 3);
    for (int i = 0; i < m; i++)
    {
        scanf("%d %d", &x, &y);
        v[x].adj.push_back(y);
        deg[y]++;
    }
    solve();

    fclose(stdin);
    fclose(stdout);
    return 0;
}