Cod sursa(job #783004)

Utilizator alexalghisiAlghisi Alessandro Paolo alexalghisi Data 1 septembrie 2012 22:53:25
Problema Ciclu Eulerian Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.26 kb
#include <cstdio>
#include <vector>
#include <stack>
using namespace std;

int n;
vector<pair<int,int> > lista[1505];
bool viz[1125755];
vector<int> v;
stack<int> stiva;

int main()
{
	freopen("domino2.in","r", stdin);
	freopen("domino2.out","w", stdout);
	scanf("%d",&n);
	if(n==2)
	{
		printf("1 1\n1 2\n2 2");
		return 0;
	}
	fclose(stdin);
	int indice=0;
	for(int i=1;i<=n;i++)
		for(int j=i;j<=n;j++)
		{
			lista[i].push_back(make_pair(++indice,j));
			lista[j].push_back(make_pair(indice,i));
		}
	for(int i=1;i<=n;i++)
	{
		if(lista[i].size()%2==1)
		{
			printf("-1");
			return 0;
		}
	}
	
	stiva.push(1);
	while(!stiva.empty())
	{
		int nod=stiva.top();
		bool ok=true;
		while(lista[nod].size())
		{
			if(viz[lista[nod].back().first]==0)
			{
				viz[lista[nod].back().first]=1;
				int next_nod=lista[nod].back().second;
				lista[nod].pop_back();
				
				stiva.push(next_nod);
				ok=false;
				break;
				
			}
			else
				lista[nod].pop_back();
		}
	
	if(ok==false) // se apeleaza urmatorul nivel
		continue;
	stiva.pop();
	v.push_back(nod);
		
		
		
	
	}
	
	
	
	for(unsigned int i=1;i<v.size();i++)
	{
		printf("%d %d\n",v[i-1],v[i]);
		
	}		
	fclose(stdin);
	fclose(stdout);
	return 0;
}