2712951_mle.cpp

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

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

using namespace std;

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

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

void SetNull(trie *t)
{
	int i;

	for (i = 0; i < 28; i++)
		t->next[i] = NULL;
}

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

	if (t->next[str[0]-'a']==NULL)
	{
		p = INIT;
		SetNull(p);
		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[13], b[13];
	int l, r, i;
	trie *root;
	int input = 1;

	root = INIT;
	SetNull(root);
	memset(visited,0,sizeof(visited));
	memset(din,0,sizeof(din));
	while (scanf("%s%s",a,b)==2)
	{
		input = 0;
		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]++;din[l]--;
	}
	if (input)
	{
		printf("Possible\n");
		return 0;
	}
	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])
		{
			num++;
			if (din[i]==1)
				f1 = 0;
			if (din[i]==-1)
				f2 = 0;
		}
	}
	if(num==0||(num==2&&!f1&&!f2))
		printf("Possible\n");
	else
		printf("Impossible\n");
	return 0;
}