学步园

我这里都不好意思把这个叫做解题报告，因为开始完全什么都不懂，然后看别人的解题报告，纯粹是一个理解过程

给自己留下个纪念,。能帮到别人是更好的咯....

讲讲自己从开始的什么都不懂，到现在略懂一点的理解:
最开始看这个链接的解题报告，很多地方看不懂

http://blog.sina.com.cn/s/blog_5cd4cccf0100apd1.html

大家可以先看看，理解题目意思，和基本思路，关于思路中的并査集，和trie树，我却都看不懂，于是，又百度

****************** 初步了解trie树 

http://www.cppblog.com/abilitytao/archive/2009/04/21/80598.html

****************** 初步了解并査集 

http://wenku.baidu.com/view/f55a0d26aaea998fcc220e8f.html

基于看了并査集，花了一定的时间做了poj2524 ，一个简单的并査集题目，并发表了解题报告，（第一次发实际上就是
代码，加代码注释）,建议刚开始和我一样的小白可以先试试

 初步了解以上的信息后，下面结合上面高手的解题报告和代码，进行自己的小白理解.....
 首先一个，关于什么父亲节点，实际上就是一个int的数组，比如一棵树：
 1--2--3--4--5,5号节点的父亲节点就是4，就这样来存储a[5]=4;
*/

#include<stdio.h>
#include<string.h>

#define MAX 500005
int num;//标记颜色种类
int indegree[MAX];//标记每种颜色出现次数，理解为图每个节点的度...
int father[MAX];//查并集用到，存父亲节点
//#define NULL 0 不一定要宏定义,后面的memset就直接设为0

//结构体字典树
struct trie_tree 
{
 int n;     //以本字母开头，后面有多少子树
 trie_tree *next[26];
 /*trie_tree()//这里可以有一个默认方式，以至于后面不要init？？？？？？
 {
  n=0;
  memset();
 }*/
}*head;

//这里就是字典树的操作
void init(trie_tree *&tree)// 要* &tree才能改变tree的指向，不然就runtime error
{
 tree=new trie_tree;
 tree->n=-1;
 memset(tree->next,0,sizeof(tree->next));//这里用sizeof和直接26有区别，不能用26 runtime error，memset包含头文件string.h
}

//获得这个颜色的num号，如过是新出现的颜色，则他的号码是累积num的结果同时做一个插入树的操作
//这里就是字典树的操作
int insert(char *str)
{
 trie_tree *p;
 p=head;
 int i=0;
 while(str[i])
 {
  if(p->next[str[i]-'a'] == 0)//出现新的颜色，再次做一个插入操作
   init(p->next[str[i]-'a']);//结合字典树链接理解
  p=p->next[str[i]-'a'];
  i++;
 }
 if(p->n == -1)//如果这个是一个新的颜色，就num++并赋值
   p->n=num++;
 return p->n;
}
//下面是并査集的find方法
/*int find(int k)
{
 while(k!=father[k])//main中后面用到了合并
  k=father[k];
 return k;
}*/
// 并査集递归调用,用这个比上面注释了的节约那么几百ms
int find(int k)
{
 if(k!=father[k])
  father[k]=find(father[k]);
 return father[k];
}

int liantong()//判断联通 看看每个颜色的祖先是不是同一个
{
 int e=find(0);  //这里之所以不能随意找一个， 然后与其他的祖先对比是因为main中开始就把0设为根节点
 for(int i=1;i<num;i++)//这里从1到 num-1？？i<=num就WA啦
  if(find(i) != e)
   return 0;
 return 1;
}
int huilu()//判断是否回路 看看有咩有奇读顶点，或者有两个
{
 int t=0;
 for(int i=0;i<num;i++)//这里为什么从0开始到num-1就结束？理由同上
  if(indegree[i]%2 != 0)
   t++;
 if(t>2)
  return 0;
 else
  return 1;
}

int main()
{
 char str_1[11],str_2[11];
 int a,b;
 num=0;//颜色种类初始化
 //for(int i=0;i<MAX;i++)
 // father[i]=i;
 init(head);
 while(scanf("%s%s",str_1,str_2)!=EOF)
 {
  a=insert(str_1);
  b=insert(str_2);
  indegree[a]++;
  indegree[b]++;
  father[find(a)]=find(b);//寻找祖先节点，合并
 }
 if(!liantong() || !huilu())
  printf("Impossible\n");
 else
  printf("Possible\n");
 return 0;
}