Cod sursa(job #2334683)

Utilizator Dragne.Andrei11Dragne Andrei Dragne.Andrei11 Data 2 februarie 2019 21:17:36
Problema Sortare topologica Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.8 kb
#include <bits/stdc++.h>

using namespace std;

const int nmax=50005;

vector <int> g[nmax];
vector <int> g_r[nmax];
vector <int> rasp;
vector <int> aux;

bool visited[nmax];
bool modif;

struct numere
{
    int priority;
    int val;
}v[nmax];

void dfs_pri(int start_node)
{
    visited[start_node]=true;
    v[start_node].priority++;
    for(int i=0;i<g[start_node].size();i++)
    {
        if(visited[g[start_node][i]]==false)
        {
            dfs_pri(g[start_node][i]);
            v[start_node].priority+=v[g[start_node][i]].priority;
        }
    }
}

bool cmp(numere a, numere b)
{
    if(a.priority==b.priority)
        return a.val<b.val;
    return a.priority<b.priority;
}

void dfs_afis(int start_node)
{
    visited[start_node]=true;
    aux.push_back(start_node);
    for(int i=0;i<g_r[start_node].size();i++)
        if(visited[g_r[start_node][i]]==false)
            dfs_afis(g_r[start_node][i]);
}

int main()
{
    freopen("sortaret.in", "r", stdin);
    freopen("sortaret.out", "w", stdout);
    int n, m;

    scanf("%d%d", &n, &m);
    for(int i=1;i<=m;i++)
    {
        int x, y;
        scanf("%d%d", &x, &y);
        g[x].push_back(y);
        g_r[y].push_back(x);
    }
    for(int i=1;i<=n;i++)
    {
        v[i].val=i;
        if(visited[i]==false)
            dfs_pri(i);
    }
    sort(v+1, v+n+1, cmp);
    memset(visited, false, sizeof(visited));
    for(int i=1;i<=n;i++)
    {
        if(visited[v[i].val]==false)
        {
            dfs_afis(v[i].val);
            reverse(aux.begin(), aux.end());
            for(int i=0;i<aux.size();i++)
                rasp.push_back(aux[i]);
            aux.clear();
        }
    }
    for(int i=0;i<n;i++)
        printf("%d ", rasp[i]);
    printf("\n");

    return 0;
}