首页 > 代码库 > Quicksearch2513
Quicksearch2513
http://blog.csdn.net/lyy289065406/article/details/6647445
图G的一个回路，若它恰通过G中每条边一次,则称该回路为欧拉(Euler)回路
1.定理：无向图G有欧拉通路的充分必要条件是G为连通图，并且G仅有两个奇度结点或者无奇度结点。
（1）当G是仅有两个奇度结点的连通图时，G的欧拉通路必以此两个结点为端点。
（2）当G是无奇度结点的连通图时，G必有欧拉回路。
2.一个有向图D具有欧拉通路，当且仅当D是连通的，且除了两个顶点外，其余顶点的入度均等于出度，这两个特殊的顶点中，一个顶点的入度比出度大１，另一个顶点的入度比出度小１． 推论：一个有向图D是欧拉图（具有欧拉回路），当且仅当D是连通的，且所有顶点的出度等于入度。
题意：给定一些木棒，木棒两端都涂上颜色，求是否能将木棒首尾相接，连成一条直线，要求不同木棒相接的一边必须是相同颜色的。
给定一张图，每个点是一种颜色，用一个单词表示，求是否能将木棒首尾相接（即欧拉回路），连成一条直线，要求不同木棒相接的一边必须是相同颜色的。此处为无向图
由图论知识可以知道，无向图存在欧拉路的充要条件为：
① 图是连通的；
② 所有节点的度为偶数，或者有且只有两个度为奇数的节点。
节点的度用颜色出现次数来统计，如样例中，蓝色blue出现三次（不管是出度还是入度），那么blue结点的度就为3
证明①图的连通性，使用并查集MergeSet是非常高效的方法。
由于并查集必须利用 数组的下标 与 存储的对象，使用int是比较方便的处理方法，但是题目的“颜色结点”是string，不方便用来使用并查集，即使用map也不行，虽然STL的map是基于hash的基础上，但并不高效，在本题中使用会超时。
为此可以使用Trie字典树，得到每个颜色单词对应的int编号id ，可以说利用Trie把string一一映射到int
/* TrieTree + MergeSet + EulerPath*///Memory Time//77460K 2047MS #include<iostream>using namespace std; const int large=500000; //25W条棒子，有50W个端点class TrieTree_Node //字典树结点{ public: bool flag; //标记某个单词是否已经结束 int id; //当前颜色(结点)的编号。这里必须要在每个节点存储一个标志作用，否则就算知道该几点是结束字符，也不知道他对应的ID号，当然，如果对应的是另外的一个STRING,这里不用存string，可以存ID号，该ID号指向特定的一维STRING数组 TrieTree_Node* next[27]; TrieTree_Node() //initial { flag=false; id=0; memset(next,0,sizeof(next)); //0 <-> NULL }}root; //类定义后面直接接名称，表示申明了一个类变量rootint color=0; //颜色编号指针，最终为颜色总个数int degree[large+1]={0}; //第id个结点的总度数int ancestor[large+1]; //第id个结点祖先/*寻找x结点的最终祖先*/int find(int x){ if(ancestor[x]!=x) ancestor[x]=find(ancestor[x]); //路径压缩 return ancestor[x];}/*合并a、b两个集合*/void union_set(int a,int b){ int pa=find(a); int pb=find(b); ancestor[pb]=pa; //使a的祖先 作为 b的祖先 return;}//利用字典树构造字符串s到编号int的映射int hash(char *s) { TrieTree_Node* p=&root; //从TrieTree的根节点出发搜索单词(单词不存在则创建) int len=0; while(s[len]!=‘\0‘) { int index=s[len++]-‘a‘; //把小写字母a~z映射到数字的1~26，作为字典树的每一层的索引 if(!p->next[index]) //当索引不存在时，构建索引 p->next[index]=new TrieTree_Node; p=p->next[index]; } if(p->flag) //颜色单词已存在 return p->id; //返回其编号 else //否则创建单词 { p->flag=true;//结束标志 p->id=++color; return p->id; //返回分配给新颜色的编号 }}int main(void) { /*Initial the Merge-Set*/ for(int k=1;k<=large;k++) //初始化，每个结点作为一个独立集合 ancestor[k]=k; //对于只有一个结点x的集合，x的祖先就是它本身 /*Input*/ char a[11],b[11]; while(cin>>a>>b) { /*Creat the TrieTree*/ int i=hash(a); int j=hash(b); //将颜色转化成数字 /*Get all nodes‘ degree*/ degree[i]++; degree[j]++; //记录a、b颜色出现的次数(总度数) /*Creat the Merge-Set*/ union_set(i,j); } /*Judge the Euler-Path*/ int s=find(1); //若图为连通图，则s为所有结点的祖先 //若图为非连通图，s为所有祖先中的其中一个祖先 int num=0; //度数为奇数的结点个数 for(int i=1;i<=color;i++) { if(degree[i]%2==1) num++; if(num>2) //度数为奇数的结点数大于3，欧拉路必不存在 { cout<<"Impossible"<<endl; return 0; } if(find(i)!=s) //存在多个祖先，图为森林，不连通 { cout<<"Impossible"<<endl; return 0; } } if(num==1) //度数为奇数的结点数等于1，欧拉路必不存在 cout<<"Impossible"<<endl; else //度数为奇数的结点数恰好等于2或不存在，存在欧拉路 cout<<"Possible"<<endl; return 0;}
Quicksearch2513