Cod sursa(job #507413)

Utilizator GodiesVlad Voicu Godies Data 5 decembrie 2010 22:53:43
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.35 kb
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <vector>

#define maxn 100000
#define maxm 50000

using namespace std;

vector<int> *v = new vector<int> [maxn];
vector<int> noi (maxn);
vector<int> visited (maxn);
vector<int> final;
void getNoIncoming()
{
    int i;
    for (i = 0; i < maxn; i++) {
        for(int j = 0; j < v[i].size(); j++) {
            noi[v[i][j]] = 1;
        }
    }
}

void bfs(int x) {
    int i;
    for (i = 0; i < v[x].size(); i++) {
        bfs(v[x][i]);
    }
    if (!visited[x]) {
        visited[x] = 1;
        final.push_back(x);
    }
}

int main() {
    unsigned int i, x, y, n, m;
    FILE *f = fopen("sortaret.in", "rt");
    FILE *g = fopen("sortaret.out", "wt");
    fscanf(f , "%d%d", &n, &m);
    for (i = 0; i < n; i++) {
        fscanf(f, "%d%d", &x, &y);
        v[--x].push_back(--y);
    }
 /*   for (i = 0; i < n; i++) {
        cout << i << " ";
        for (int j = 0; j < v[i].size();j++) {
            cout << v[i][j] << " ";
        }
        cout << endl;
    } */
    getNoIncoming();
    for (i = 0; i < n; i++) {
        if (noi[i] == 0)
            bfs(i);
    }
    for (vector<int>::reverse_iterator it = final.rbegin(); it != final.rend(); ++it) {
        fprintf(g, "%d ", *it + 1);
    }
    fclose(f);
    fclose(g);
    return 0;
}