3260522_ac_266ms_7552k.cpp

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

#include <string>
#include <vector>
#include <algorithm>
#define maxn 10000

using namespace std;

struct point
{
	char x[300], y[300];

	bool operator < (const point &that)	const
	{
		if(strcmp(x,that.x)==0)
			return strcmp(that.y,y) > 0;
		else
			return strcmp(that.x,x) > 0;
	}
	bool operator == (const point &that)	const
	{
		return strcmp(that.x,x)==0&&strcmp(that.y,y)==0;
	}
};

struct segment
{
	point st, ed;
};

int k, n, cnt, d[maxn], visited[maxn];
point p[maxn];
segment s[maxn];

vector <int> map[6000];

void dfs(int v)
{
	int i;

	visited[v] = 1;
	cnt++;
	for(i = 0; i < map[v].size(); i++)
	{
		if(!visited[map[v][i]])
		{
			dfs(map[v][i]);
		}
	}
}

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

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

int getId(point t)
{
	int min, max, mid;

	min = 0;max = n-1;
	while(min <= max)
	{
		mid = (min+max)>>1;
		if(t==p[mid])
			return mid;
		if(t<p[mid])
			max = mid-1;
		else
			min = mid+1;
	}
	return -1;
}

int main()
{
	int i, m;

	scanf("%d",&k);
	for(i = 0; i < k; i++)
	{
		scanf("%s%s%s%s",p[i*2].x,p[i*2].y,p[i*2+1].x,p[i*2+1].y);
		modify(p[i*2].x);
		modify(p[i*2].y);
		modify(p[i*2+1].x);
		modify(p[i*2+1].y);
		s[i].st = p[i*2];
		s[i].ed = p[i*2+1];
	}
	sort(p,p+2*k);
	for(i = 0, n = 0; i < 2*k; i++,n++)
	{
		p[n] = p[i];
		m = i;
		while(m<2*k&&p[m]==p[n])
			m++;
		i = m-1;
	}
	for(i = 0; i < n; i++)
	{
		d[i] = 0;
	}
	for(i = 0; i < k; i++)
	{
		int ii, jj;

		ii = getId(s[i].st);
		jj = getId(s[i].ed);
		d[ii]++;d[jj]++;
		
		map[ii].push_back(jj);
		map[jj].push_back(ii);
	}
	cnt = 0;
	memset(visited,0,sizeof(visited));
	dfs(0);
	if(cnt!=n)
	{
		puts("0");
		return 0;
	}
	for(i = 0; i < n; i++)
	{
		if(d[i]%2==1)
		{
			puts("0");
			return 0;
		}
	}
	puts("1");
	return 0;
}