Cod sursa(job #2155456)

Utilizator Daniel_MocsiMocsi Daniel Andrei Daniel_Mocsi Data 7 martie 2018 20:55:56
Problema Sortare topologica Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 0.97 kb
#include <iostream>
#include <fstream>
#include <vector>
#define NMAX 101
using namespace std;

ifstream f("sortaret.in");
ofstream g("sortaret.out");

struct node {
    int val;
    node* next;
};

node *G[NMAX], *sol;
vector<int> gf[NMAX];
int n, m, viz[NMAX];

void addNode(node* &p, int val) {
    node* q = new node;
    q->val = val;
    q->next = p;
    p = q;
}

void DFS(int s) {
    viz[s] = 1;
    //for (node* i = G[s]; i; i=i->next)
    //    if (!viz[i->val])
    //        DFS(i->val);
    for (int i = 0; i < (int)gf[s].size(); ++i)
        if (!viz[gf[s][i]])
            DFS(gf[s][i]);
    addNode(sol, s);
}

int main()
{
    f >> n >> m;
    for (int i = 0, n1, n2; i < m; ++i) {
        f >> n1 >> n2;
        //addNode(G[n1], n2);
        gf[n1].push_back(n2);
    }
    for (int i = 1; i <= n; ++i)
        if (!viz[i])
            DFS(i);
    for (node* i = sol; i; i=i->next)
        g << i->val << ' ';
    return 0;
}