2700843_tle.cpp

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

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <vector>
#define INIT (Tree *)malloc(sizeof(Tree))

using namespace std;

typedef struct node
{
	char id[11];
	int no;
	struct node *l, *r;
}Tree;

Tree *root;
int mark, no, num;
int dout[250001], din[250001], visited[250001];

vector <int> tree[250001];

int insert(char str[])
{
	Tree *p, *q;
	int t;

	if(mark)
	{
		root = INIT;
		root->no = no++;
		strcpy(root->id,str);
		root->l = root->r = NULL;
		mark = 0;
		return 0;
	}
	p = root;
	q = INIT;
	strcpy(q->id,str);
	q->l = q->r = NULL;
	while(p)
	{
		t = strcmp(p->id,str);
		if(t>0)
		{
			if(p->l)
				p = p->l;
			else
			{
				q->no = no++;
				p->l = q;
				return no-1;
			}
		}
		else 
			if(t<0)
			{
				if(p->r)
					p = p->r;
				else
				{
					q->no = no++;
					p->r = q;
					return no-1;
				}
			}
			else
				return p->no;
	}
	return -1;
}

void dfs(int v)
{
	int i;

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

int main()
{
	int i, l, r;
	char a[11], b[11];

	mark = 1;no = 0;
	memset(din,0,sizeof(din));
	memset(dout,0,sizeof(dout));
	while(scanf("%s",a)==1)
	{
		l = insert(a);
		scanf("%s",b);
		r = insert(b);
		tree[l].push_back(r);
		tree[r].push_back(l);
		din[r]++;dout[l]++;
	}
	num = 0;
	dfs(0);
	if(num!=no)
	{
		printf("Impossible\n");
		return 0;
	}
	no = 0;
	int f1, f2;
	f1 = f2 = 0;
	for(i = 0; i < no; i++)
	{
		if(din[i]!=dout[i])
		{
			no++;
			if(din[i]-dout[i]==1)
				f1 = 1;
			if(dout[i]-din[i]==1)
				f2 = 1;
		}
	}
	if(!no||(no==2&&f1&&f2))
		printf("Possible\n");
	else
		printf("Impossible\n");
	return 0;
}