Cod sursa(job #1962482)

Utilizator linerunnerMihai Ion linerunner Data 11 aprilie 2017 20:11:59
Problema Sortare topologica Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.48 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) {
			src = i;
			check[i] = 1;
			break;
		}
	}

	q.push(src);
	fprintf(f, "%d ", src);

	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;
				break;
			}
		}
	}

	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;
}