Cod sursa(job #1430317)

Utilizator sing_exFMIGhita Tudor sing_ex Data 8 mai 2015 10:10:11
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.99 kb
#include <iostream>
#include <vector>
#include <deque>
#include <stdio.h>

using namespace std;

vector <int> *s;
deque <int> tpl;
int *viz;

void dfs(int x) {
    int i;
    for (i=0;(unsigned)i<s[x].size();i++) {
        if (!viz[s[x][i]]) {
            viz[s[x][i]] = 1;
            dfs(s[x][i]);
        }
    }
    tpl.push_back(x);
}

int main()
{
    int n,i,j,m,x;
    FILE *f,*g;
    f = fopen("sortaret.in","r");
    g = fopen("sortaret.out","w");
    fscanf(f,"%d %d",&n,&m);
    s = new vector<int>[n+1];
    viz = new int[n+1];
    for (i=1;i<=n;i++) viz[i] = 0;
    for (i=1;i<=m;i++) {
        fscanf(f,"%d %d",&x,&j);
        s[x].push_back(j);
        viz[j] = 1;
    }
    fclose(f);
    for (i=1;i<=n;i++)
        if (!viz[i]) break;
    x = i;
    for (i=1;i<=n;i++) viz[i] = 0;
    dfs(x);
    for (i=0;i<=n;i++)
        if (!viz[i]) tpl.push_front(i);
    for (i=tpl.size()-1;i>=0;i--) fprintf(g,"%d ",tpl[i]);
    fclose(g);
    return 0;
}