3260303_wa.cpp

北大大牛代码 1240道题的原代码 超级权威

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

int size;

struct node
{
	int l, r;
	char x[250], y[250];
}btree[6000];

void modify(char str[])
{
	int i, l;

	l = strlen(str);
	for(i = 0; i < l-1; i++)
	{
		if(str[i]!='0')
		{
			break;
		}
	}
	strcpy(str,&str[i]);
}

int insert(char x[],char y[])
{
	int no, vx, vy;

	no = 0;
	while(no!=-1)
	{
		vx = strcmp(x,btree[no].x);
		vy = strcmp(y,btree[no].y);
		if(vx==0&&vy==0)
		{
			return no;
		}
		if(vx>0||(vx==0&&vy>0))
		{
			if(btree[no].r==-1)
			{
				btree[no].r = size;
				strcpy(btree[size].x,x);
				strcpy(btree[size].y,y);
				btree[size].l = btree[size].r = -1;
				return size++;
			}
			else
				no = btree[no].r;
		}
		else
		{
			if(btree[no].l==-1)
			{
				btree[no].l = size;
				strcpy(btree[size].x,x);
				strcpy(btree[size].y,y);
				btree[size].l = btree[size].r = -1;
				return size++;
			}
			else
				no = btree[no].l;
		}
	}
	return 1;
}

int degree[6000];

int add(char x[],char y[])
{
	int id;

	modify(x);modify(y);
	if(size==0)
	{
		id = size++;
		btree[0].l = btree[0].r = -1;
		strcpy(btree[0].x,x);
		strcpy(btree[0].y,y);
	}
	else
	{
		id = insert(x,y);
	}
	degree[id]++;
	return id;
}

int f[6000];

int find(int p)
{
	if(f[p]!=p)
		return f[p]=find(f[p]);
	else
		return f[p];
}

int main()
{
	int k, j, i, id[2];
	int s1, s2;
	char x[250], y[250];

	scanf("%d",&k);
	size = 0;
	for(i = 0; i < 2*k; i++)
	{
		f[i] = i;
	}
	for(i = 0; i < k; i++)
	{
		for(j = 0; j < 2; j++)
		{
			scanf("%s%s",x,y);
			id[j] = add(x,y);
		}
		s1 = find(id[0]);
		s2 = find(id[1]);
		f[s1] = s2;
	}
	for(i = 1; i < size; i++)
	{
		if(f[i]!=f[0])
		{
			puts("0");
			return 0;
		}
	}
	for(i = 0; i < size; i++)
	{
		if(degree[i]%2!=0)
		{
			puts("0");
			return 0;
		}
	}
	puts("1");
	return 0;
}