POJ--2513 Colored Sticks

港控/mmm° 2022-08-10 13:48 3阅读 0赞

这一题本能的想法就是把所有的单词都读入，统计一下每种单词的个数，判断是否构成欧拉通路，判断图是否连通。

可是可是题目给的不是数字而是单词，着我该怎么办？？？

数字是否连通还可以用并查集，但字符串怎么办。难道要用map，用map<char ,char> 实现并查集，那每种颜色的数量怎么办，用map<char ,int>?

不过map中的查找好像是自平衡的红黑树复杂度为O log（N）这里的N最大是25w，但是最坏的情况，要查找log（25w！）（可能算错了），看起来有点恐怖，果断先放下吧；看了别人的博客，发现好像是用  Trie树 实现的，再用了一些小技巧，就把巧妙地解决了问题，技不如人...........

此题的解题思路：  
有明的七桥问题大家都知道，而这一题就是七桥问题的变形，运用欧拉的“[一笔画定理][Link 1]”判断该图是否是欧拉通路。

当然判断欧拉通路后还必须判断他是不是 连通图。

贴代码：

#include <cstdio>
    #include <cstdlib>
    #include <cstring>
    #include <iostream>
    #define maxn 300000 //const int maxn=300000;
    using namespace std;
    
    struct Trie
    {
    	int code;
    	Trie *next[26];
    };
    Trie root;
    
    void initi(Trie *q)
    {
    	for(int i=0;i<26;i++)
    		q->next[i]=NULL;
    	q->code=0;
    } 
    
    void creatTrie(char *str,int x)
    {
    	int len=strlen(str);
    	Trie *p=&root,*q;
    	for(int i=0;i<len;i++)
    	{
    		int id=str[i]-'a';
    		if(p->next[id]==NULL)
    		{
    			q=(Trie *)malloc(sizeof(root));//可用静态数组，速度更快一些，不过可能数组小了RE，大了浪费内存
    			initi(q);
    			p->next[id]=q;
    			p=q;
    		}
    		else 
    			p=p->next[id];
    	}
    	p->code=x;
    }
    int findTrie(char *str)
    {
    	Trie *p=&root;
    	int len=strlen(str);
    	for(int i=0;i<len;i++)
    	{
    		int id=str[i]-'a';
    		p=p->next[id];
    		if(p==NULL)
    			return 0;
    	}
    	return p->code;
    }
    int pa[maxn],numb[maxn];//父亲节点数组，节点的通路个数，以下是并查集
    
    int find(int x)
    {
    	int r=pa[x];
    	while(r!=pa[r])
    		r=pa[r];
    	while(x!=r)
    	{
    		int temp=pa[x];
    		pa[x]=r;
    		x=temp;
    	}
    	return r;	
    }
    void make_set(int x,int y)
    {
    	int px=find(x),py=find(y);
    	if(px!=py)
    	{
    		pa[px]=py;
    	}
    }
    void initial()
    {
    	for(int i=0;i<maxn;i++)
    	{
    		pa[i]=i;
    	}
    	memset(numb,0,sizeof(numb));
    }
    
    bool judge(int cnt)
    {
    	int count=0;
    	for(int i=1;i<=cnt;i++)//欧拉通路的判断
    	{
    		if(numb[i]%2==1)count++;
    	}
    	if(count!=0&&count!=2)return false;
    	int k=find(1);//连通图判断
    	for(int i=2;i<=cnt;i++)
    		if(k!=find(i))return false;
    	return true;
    }
    int main()
    {
    	char s1[15],s2[15];
    	int cnt=0,x,y;
    	initi(&root);
    	initial();
    //	freopen("in.txt","r",stdin);
    	while(scanf("%s%s",s1,s2)!=EOF)
    	{
    		x=findTrie(s1);
    		y=findTrie(s2);
    		if(x==0)creatTrie(s1,x=++cnt);
    		if(y==0)creatTrie(s2,y=++cnt);
    		numb[x]++;numb[y]++;
    		make_set(x,y);
    	}
    
    	if(judge(cnt))printf("Possible\n");
    	else printf("Impossible\n");
    	return 0;		
    }

[Link 1]: http://zh.wikipedia.org/wiki/%E4%B8%80%E7%AC%94%E7%94%BB%E9%97%AE%E9%A2%98