pku 2513 字典树+欧拉回路.txt

ACM资料大集合

#include <stdio.h>
#include <malloc.h>
#include <iterator>
#include <vector>
using namespace std;

//PKU 2513 字典树+欧拉回路
#define NMAX 250100
typedef  struct tire
{
   struct tire *next[27];
   char date;
   int cnt;
   int number;
}*_tire;

vector <int> node[2*NMAX];
int visited[2*NMAX];
int countc[2*NMAX];
int cixu;

int init_tire(_tire root, char *string)
{
    _tire s;
    s=root;
    
    while(*string!='\0')
    {
       if(s->next[*string - 'a']==NULL)
       {
          s->next[*string - 'a'] = (_tire)malloc(sizeof(struct tire));
          (s->next[*string - 'a'])->date = *string;
		  (s->next[*string - 'a'])->cnt = 0;
          s = s->next[*string - 'a'];
          for(int i=0;i<26;i++)
          {
              s->next[i] = NULL;
          }
       }
       else
       {
          s = s->next[*string - 'a'];
       }
       string++;
    }
    
//	if(s->cnt==0)
//	{
		s->cnt=1;
		s->number = ++cixu;
//	}
	return s->number;
}

void print(_tire root, char *s, int i)
{
    int j;
    s[i] = root->date;

    if(root->cnt==1)
    {
		s[i+1] = 0;
		printf("cixu=%d ",root->number);
        puts(s);
    }
    
    for(j=0;j<26;j++)
    {
        if(root->next[j]!=NULL)
        {
           print(root->next[j],s,i+1);
        }
    }
}

int find(_tire root,char *key,int i)
{
	int j,ans;
//	printf("root=%c\n",root->date);
	if(root->cnt==1 && key[i]=='\0') 
	{
		return root->number;
	}
	for(j=0;j<26;j++)
	{
		if(root->next[j]!=NULL && (root->next[j])->date==key[i])
		{
			ans=find(root->next[j],key,i+1);
			if(ans>=0) return ans;
		}
	}
	return -1;
}

void dfs(int p)
{	
	vector<int>::iterator iter;
	visited[p]=1;
//	printf("p=%d\n",p);
	for(iter=node[p].begin();iter!=node[p].end();iter++)
	{
		if(visited[*iter]==0) dfs(*iter);
	}
}
int main()
{
    _tire root;
    int m,i,ta,tb,dnum=0,start=0,sum=0;
    char s[265],sa[265];
	cixu=0;
    
    root = (_tire)malloc(sizeof(struct tire));
	memset(countc,0,sizeof(countc));
	memset(visited,0,sizeof(visited));
//   puts("输入字符串个数：");
    for(i=0;i<26;i++)
    {
       root->next[i]=NULL;
    }
	while(scanf("%s %s",&s,&sa)!=EOF)
	{//无输入时返回Possible
		start=1;
		ta=find(root,s,0);
		tb=find(root,sa,0);
		if(ta==-1) {dnum++;ta=init_tire(root,s);}
		if(tb==-1) {dnum++;tb=init_tire(root,sa);}
		node[ta].push_back(tb);
		node[tb].push_back(ta);
		countc[ta]++;
		countc[tb]++;
	}
	dfs(1);
	for(i=1;i<=dnum;i++)
	{
		if(visited[i]==0)
		{
			printf("Impossible\n");
			return 0;
		}
	}
	for(i=1;i<=dnum;i++)
	{
		sum+=countc[i]%2;
	}
	if(sum==0 || sum==2) printf("Possible\n");
	else 	printf("Impossible\n");
	return 0;
//	}
//    scanf("%d",&m);
//    getchar();
//   while(m--)
//    {
//       gets(s);
//       init_tire(root,s);
//    }
//    puts("\n依字典排序后：");
//    for(i=0;i<26;i++)
//    {
//       if(root->next[i] != NULL)
//       {
//          print(root->next[i],s,0);
//       }
//    }
//	while(scanf("%s",&s)!=EOF)
//	{
//	printf("find=%d\n",find(root,s,0));
//	}
//    return 0;
}

/*
#include<map>
#include<iterator>
#include<vector>
#include<string>
#include<stdio.h>
using namespace std;
bool v[251000];
vector<int> vect[551000];
void dfs(int x)
{
	vector<int>::iterator iter;
	if(v[x]==1) return ;
	else v[x]=1;
//	printf("x=%d\n",x);
	for(iter=vect[x].begin();iter!=vect[x].end();iter++)
		dfs(*iter);
}
int main()
{
	char a[24],b[24];
    int sum=0,i,c=1,start=0;
	map<string,int>map1,map2;
	map<string,int>::iterator iter;
	memset(v,0,sizeof(v));
//	freopen("in.txt","r",stdin);
	while(scanf("%s%s",a,b)!=EOF)
	{
		start=1;
		int t1=map2[a],t2=map2[b];
		if(!t1)t1=map2[a]=c++;
		if(!t2)t2=map2[b]=c++;
		vect[t1].push_back(t2);
		vect[t2].push_back(t1);
		map1[a]++;map1[b]++;
	}
	if(start==1) dfs(1);
	else {printf("Possible\n");return 0;}
//	printf("111\n");
	for(i=1;i<c;i++)
		if(!v[i]) break;
	if(i<c) {printf("Impossible\n"); return 0;}
	for(iter=map1.begin();iter!=map1.end();iter++)
		sum+=iter->second%2;
    if(sum==2||sum!=0) printf("Possible\n");
	else printf("Impossible\n");
	return 0;
}
*/
//2513
/*
#include <stdio.h>
#include <stdlib.h>
#include <map>
#include <string>
using namespace std;

char a[11], b[11];
struct Node
{
	Node(const string &str): degree(1), rank(0), p(str){}
	int degree;
	int rank;
	string p;
};

typedef map<string, Node *> Map;
typedef Map::value_type MVT;
typedef Map::iterator Iter;
Map mp;
Iter iter;

void link(const string &x, const string &y)
{
	if(mp[x]->rank > mp[y]->rank)
		mp[y]->p = x;
	else
	{
		mp[x]->p = y;
		if(mp[x]->rank == mp[y]->rank)
			mp[y]->rank++;
	}
}

const string &find_set(const string &x)
{
	if(x != mp[x]->p)
		mp[x]->p = find_set(mp[x]->p);
	return mp[x]->p;
}

void join(const string &x, const string &y)
{
	link(find_set(x), find_set(y));
}

int main()
{
	while(scanf("%s%s", a, b) != EOF)
	{
		if( (iter=mp.find(a)) == mp.end() )
			mp.insert(MVT(a, new Node(a)));
		else
			iter->second->degree++;
		if( (iter=mp.find(b)) == mp.end() )
			mp.insert(MVT(b, new Node(b)));
		else
			iter->second->degree++;

		join(a, b);
	}
	
	iter = mp.begin();
	const string &str = find_set(iter->first);
	iter++;
	for(; iter != mp.end(); iter++)
	{
		if(find_set(iter->first) != str)
		{
			printf("Impossible\n");
			return 0;
		}
	}
	
	int count = 0;
	for(iter = mp.begin(); iter != mp.end(); iter++)
	{
		if(iter->second->degree & 1)
			count++;
	}
	if(count == 0 || count == 2)
		printf("Possible\n");
	else
		printf("Impossible\n");
}
*/