Cod sursa(job #3248521)

Utilizator popuPop Matei Tudor popu Data 12 octombrie 2024 09:45:01
Problema Sortare topologica Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.13 kb
#include <bits/stdc++.h>

using namespace std;

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

struct muchie
{
    int i, j;
};

struct GOA
{
    int n, m;
    vector<vector<int>> graf;
    vector<int> sortt, vis;

    void init(int n, int m)
    {
        this->n = n;
        this->m = m;
        graf.resize(n + 1);
        for(int i = 0; i <= n; i++)
            vis.push_back(0);
    }

    void addEdge(muchie x)
    {
        graf[x.i].push_back(x.j);
    }

    void dfs(int node)
    {
        vis[node] = 1;
        for(int i = 0; i < graf[node].size(); i++)
            dfs(graf[node][i]);
        sortt.push_back(node);
    }

    void makeSortt()
    {
        for(int i = 1; i <= n; i++) {
            if(!vis[i])
                dfs(i);
        }
        for(int i = n - 1; i >= 0; i--)
            fout << sortt[i] << ' ';
    }
}G;

void input()
{
    int n, m;
    fin >> n >> m;
    G.init(n, m);
    while(m--) {
        muchie x;
        fin >> x.i >> x.j;
        G.addEdge(x);
    }
}

int main()
{
    input();
    G.makeSortt();

    return 0;
}