2712242_re.cpp

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

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

using namespace std;

typedef struct node
{
	int id;
	struct node *next[27];
}trie;

int no = 0, tmp, num = 0;
vector <int> tree[250001];
int visited[250001];
int din[250001], dout[250001];

void insert(trie *t,char str[])
{
	trie *p;

	if (t->next[str[0]-'a']==NULL)
	{
		p = INIT;
		memset(p->next,NULL,sizeof(p->next));
		t->next[str[0]-'a'] = p;
		if (str[0]=='{')
		{
			t->id = no;
			tmp = no++;
			return ;
		}
		else
			insert(t->next[str[0]-'a'],&str[1]);
	}
	else
	{
		if(str[0]=='{')
		{
			tmp = t->id;
			return ;
		}
		else
			insert(t->next[str[0]-'a'],&str[1]);
	}
}

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

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

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