Cod sursa(job #2781415)

Utilizator Vlad_AnicaAnica-Popa Vlad-Ioan Vlad_Anica Data 9 octombrie 2021 13:58:19
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.04 kb
#include <iostream>
#include <stdio.h>
#include <vector>


using namespace std;
const int NMAX = 50000, MMAX = 100000, VIS = 2, NOTVIS = 1, DEG0 = 0;

vector<int> lists[NMAX + 1];
int finOrd[NMAX];
char propr[NMAX + 1];
int p;

void DFS(int node);

int main()
{
    int n, m, i, node1, node2, node;
    FILE *fin = fopen("sortaret.in", "r");
    fscanf(fin, "%d%d", &n, &m);
    for (i = 0; i < m; i++)
    {
        fscanf(fin, "%d%d", &node1, &node2);
        propr[node2] = NOTVIS;
        lists[node1].push_back(node2);
    }
    fclose(fin);

    p = 0;
    for (node = 1; node <= n; node++)
        if (propr[node] == DEG0)
            DFS(node);

    FILE *fout = fopen("sortaret.out", "w");
    for (i = n - 1; i >= 0; i--)
        fprintf(fout, "%d ", finOrd[i]);
    fclose(fout);
    return 0;
}

void DFS(int node)
{
    propr[node] = VIS;
    int len = lists[node].size();
    for (int i = 0; i < len; i++)
        if (propr[lists[node][i]] != VIS)
            DFS(lists[node][i]);
    finOrd[p++] = node;
}