Cod sursa(job #3304315)

Utilizator andrei_nAndrei Nicolae andrei_n Data 22 iulie 2025 15:04:44
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.97 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin ("sortaret.in");
ofstream fout ("sortaret.out");

vector <int> g[100001];
int n, m;
int visited[100001], in_stack[100001];
vector <int> topo_sorted;

void dfs(int nod, bool &cycle)
{
    visited[nod] = true;
    in_stack[nod] = true;
    for (int vecin : g[nod])
    {
        if (in_stack[vecin])
            cycle = true;
        if (!visited[vecin])
            dfs(vecin, cycle);
    }
    in_stack[nod] = false;
    topo_sorted.push_back(nod);
}

int main()
{
    fin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        int x, y;
        fin >> x >> y;
        g[x].push_back(y);
    }

    bool cycle = false;
    for (int nod = 1; nod <= n; nod++)
        if (!visited[nod])
            dfs(nod, cycle);

    if (cycle)
        cout << "CYCLE!";

    reverse(topo_sorted.begin(), topo_sorted.end());
    for (int nod : topo_sorted)
        fout << nod << ' ';
    return 0;
}