Mai intai trebuie sa te autentifici.
Cod sursa(job #1962487)
Utilizator | Data | 11 aprilie 2017 20:16:15 | |
---|---|---|---|
Problema | Sortare topologica | Scor | 60 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 1.44 kb |
#include <map>
#include <set>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <string>
#include <bitset>
#include <cstdio>
#include <limits>
#include <vector>
#include <climits>
#include <cstring>
#include <cstdlib>
#include <fstream>
#include <numeric>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <stdlib.h>
#include <stdio.h>
using namespace std;
#define VMAX 50002
int in_grade[VMAX];
int check[VMAX];
std::vector<int> edges[VMAX];
void kahn(int V)
{
std::queue<int> q;
int src, i;
FILE *f = fopen("sortaret.out", "w");
for (i = 1 ; i <= V ; i++) {
if (in_grade[i] == 0) {
q.push(i);
fprintf(f, "%d ", i);
check[i] = 1;
}
}
while (!q.empty()) {
int aux = q.front();
q.pop();
for(auto it = edges[aux].begin(); it != edges[aux].end(); it++) {
in_grade[*it]--;
}
for (i = 1 ; i <= V ; i++) {
if (in_grade[i] == 0 && check[i] == 0) {
q.push(i);
fprintf(f, "%d ", i);
check[i] = 1;
}
}
}
fclose(f);
}
int main()
{
int V, E;
int i, v_src, v_dst;
FILE *f = fopen("sortaret.in", "r");
fscanf(f, "%d", &V);
fscanf(f, "%d", &E);
for (i = 0 ; i < E ; i++) {
fscanf(f, "%d", &v_src);
fscanf(f, "%d", &v_dst);
edges[v_src].push_back(v_dst);
in_grade[v_dst] += 1;
}
fclose(f);
kahn(V);
return 0;
}