Cod sursa(job #2933573)

Utilizator DMR6476Erdic Dragos DMR6476 Data 5 noiembrie 2022 11:51:56
Problema Sortare topologica Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.16 kb
#include <iostream>
#include <vector>
#include <fstream>

using namespace std;
vector<vector<int> > theNeighbours;
ifstream fin("sortaret.in");
ofstream fout("sortaret.out");
vector<int> solution;
bool found[100005];
struct nod{
  int info;
  nod * urm;
  nod * last;
};

nod * prim = new nod;
void dfs(int node){
    found[node] = true;

    for(int i = 0; i < theNeighbours[node].size(); i++)
    {
        int newNode = theNeighbours[node][i];
        if(found[newNode] == false){
            dfs(newNode);
        }
    }
    nod * newNode = new nod;
    newNode ->info = node;
    newNode ->last = prim;
    prim->urm = newNode;
    prim = prim ->urm;
}

int main()
{
    int n, m;
    fin>>n>>m;
    theNeighbours = vector<vector<int> > (n + 5);
    for(int i = 0; i < m; i++){
        int firstNode, secondNode;
        cin>>firstNode>>secondNode;
        theNeighbours[firstNode].push_back(secondNode);
    }

    prim->info = 1;

    for(int i = 1; i <= n; i++){
        if(found[i] == false) dfs(i);
    }
    while(prim->last != NULL){
        fout<<prim->info<<" ";
        prim = prim->last;

    }
    return 0;
}