Cod sursa(job #2480459)

Utilizator invoIlioi Alexandru invo Data 25 octombrie 2019 17:16:28
Problema Sortare topologica Scor 60
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1 kb
#include <fstream>
#include <iostream>
#include <vector>
#define MAX 50001
using namespace std;

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

bool haveElems,visited[MAX];
int m,n,temp1,temp2;
vector<int> interior[MAX];
vector<int> exterior[MAX];

bool IsInList(vector<int>& a,int n)
{
	for (int i = 0; i < a.size(); ++i)
	{
		if (a[i] == n)
			return true;
	}
	return false;
}

int main()
{
    f>>n>>m;
    for(int i = 0;i < m;++i)
    {
        f>>temp1>>temp2;
		if (!IsInList(exterior[temp1], temp2))
		{
			exterior[temp1-1].push_back(temp2-1);
			interior[temp2-1].push_back(temp1-1);
		}
    }
	haveElems = true;
	while (haveElems)
	{
		haveElems = false;
		for (int i = 0; i < n; ++i)
		{
			if (!visited[i] && interior[i].size() == 0)
			{
				for (int j = 0; j < exterior[i].size(); ++j)
				{
					interior[exterior[i][j]].pop_back();
				}
				visited[i] = true;
				g << i + 1 << ' ';
				haveElems = true;
			}
		}
	}
	g << '\n';
    return 0;
}