101.cpp

平时acm训练时ac的源代码

#include <stdio.h>
#include <stdlib.h>

typedef struct Arc
{
	struct Arc *next;
	int adjV;
	int No;
	char flat;
}Arc;

typedef struct Vex
{
	int arcc;
	struct Arc *fArc;
}Vex;

int main(void)
{
	int N, i, a, b, counter, *M, *A, st, inp[7], ved[7];
	char *T, *U;
	struct Arc *t1, *t2;
	Vex v[7];
	for (i=0; i<7;i++ )
	{
		ved[i] = 0;
		v[i].arcc = 0;
		v[i].fArc = 0;
		inp[i] = 0;
	}
	scanf("%d", &N);
	T = new char[N];
	A = new int[N];
	M = new int[N];
	U = new char[N+1];
	for (i=0; i<N; i++)
	{
		U[i+1] = 'N';
		scanf("%d %d", &a, &b);
		inp[a] = 1;
		inp[b] = 1;
		t1 = new Arc;
		(*t1).adjV = b;
		(*t1).No = i+1;
		(*t1).flat = '-';
		t2 = v[a].fArc;
		v[a].fArc = t1;
		(*t1).next = t2;
		t1 = new Arc;
		(*t1).adjV = a;
		(*t1).No = 1+i;
		(*t1).flat = '+';
		t2 = v[b].fArc;
		v[b].fArc = t1;
		(*t1).next = t2;
		v[a].arcc += 1;
		v[b].arcc += 1;
	}
	for (b=8, a=0, i=0; i<7; i++)
	{
		if (0!=v[i].arcc%2)
		{
			a += 1;
			b = i;
		}
	}
	for (i=0; 0==inp[i]; i++);
	ved[0] = i;
	st = 0;
	int ed = 1;
	for (; st!=ed; )
	{
		t1 = v[ved[st]].fArc;
		inp[ved[st]] = 2;
		st ++;
		st = st%7;
		for (; 0!=t1; )
		{
			if (inp[(*t1).adjV]!=2)
			{
				ved[ed++] = (*t1).adjV;
				inp[(*t1).adjV]=2;
				ed=ed%7;
			}
			t1 = (*t1).next;
		}
	}
	for (i=0; i<7; i++)
	{
		if (1==inp[i])
		{
			a = 3;
			break;
		}
	}
	if (a>2)
	{
		printf("No solution");
	}
	else
	{
		if (8==b)
		{
			for (b=0; 0==v[b].fArc && b<7; b++);
		}
		st = b;
		for (i=0, counter=0; counter<N; )
		{
			for (; 0!=v[b].fArc; )
			{
				t1 = v[b].fArc;
				v[b].fArc = (*t1).next;
				if ('N'==U[(*t1).No])
				{
					T[i] = (*t1).flat;
					A[i] = (*t1).No;
					M[i] = (*t1).adjV;
					b = M[i];
					U[A[i]] = 'Y';
					i += 1;
				}
				delete t1;
			}
			for (; 0==v[b].fArc && i>0; )
			{
				counter += 1;
				i -= 1;
				printf("%d %c\n", A[i], T[i]);
				if (0!=i)
				{
					b = M[i-1];
				}
				else
				{
					b = st;
				}
			}
		}
	}
	delete A;
	delete M;
	delete T;
	delete U;
	return 0;
}