Cod sursa(job #531639)

Utilizator dornescuvladVlad Eugen Dornescu dornescuvlad Data 9 februarie 2011 23:49:48
Problema Felinare Scor 0
Compilator cpp Status done
Runda oni_2007_zi1 Marime 1.02 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

using namespace std;

const char iname[] = "felinare.in";
const char oname[] = "felinare.out";

ifstream fin(iname);
ofstream fout(oname);


int n, m, i, x, initi, mx, y, ans, j;
vector<int> Gr[8194];
int outcoming[8194], tp;

struct cmp
{
	bool operator()(const int &a, const int &b)const
	{
		if(outcoming[a] > outcoming[b])
			return 0;
		return 1;
	}
};


priority_queue<int, vector<int>, cmp> prQ;
int doki;


int main()
{
	fin >> n >> m;
	for(i = 1; i <= n; i ++)
	{
		fin >> x >> y;
		Gr[x].push_back(y);
		outcoming[x]++;
		outcoming[y]++;
	}
	for(i = 1; i <= n; i ++)
		prQ.push(i);
	while(!prQ.empty())
	{	
		doki = 1;
		++ans;
		tp = prQ.top();
		outcoming[tp] = 0;
		prQ.pop();
		for(j = 0; j < Gr[tp].size(); j++)
			outcoming[Gr[tp][j]] --;
		for(j = 1; j <= n; j ++)
			if(outcoming[j] != 0 && j != tp)
				doki = 0;
		if(doki == 1)
			break;
	}
	fout << 2 * n - ans << "\n";
	return 0;
}