学步园

题意：给你一组单词，判断能否排列这些单词使得前一个单词的最后一个字母是后一个单词的开头字母。能则打印出这样的排列。

思路：把单词的第一个字母和最后一个字母作为边的两个节点，单词作边，找欧拉路。

第一次做欧拉路的题，这一题需要首先判断有没有欧拉路，依次判断是否联通（并查集），再判断每个节点的度是否满足要求，具体欧拉路的性质见离散数学。在找欧拉路的时候自己写过一个dfs，大致是：

void Euler(int cnt)
{
    for(int i=0;i<n;i++)
    {
        if(!v[i]&&e[cnt].to==e[i].from)
        {
            v[i]=1;    printf(".%s",e[i].str);
            Euler(i);
	    break;
        }
    }
}

这样并不能正确的找到欧拉路，如果正确的欧拉路是1->3->4->5->3->2，dfs在走到3这个节点的时候优先遍历的是2，遍历2之后退出循环，并没有遍历所有的边。
摘录一段找欧拉路的算法，fleury算法的描述：
Fleury算法，能不走桥就不走桥：
　　（1）任取v0∈V(G)，令P0=v0.　　（2）设Pi=v0e1v1e2…eivi已经行遍，按下面方法来从E(G)-{e1,e2,…,ei}中选取ei+1：　　　　（a）ei+1与vi相关联；　　　　（b）除非无别的边可供行遍，否则ei+1不应该为Gi=G-{e1,e2,…,ei}中的桥。　　（3）当（2）不能再进行时，算法停止。
　　可以证明，当算法停止时所得简单回路Pm=v0e1v1e2…emvm(vm=v0)为G中一条欧拉回路。
（http://zyk.thss.tsinghua.edu.cn/73/longtime/part4/chapter15/15_01_03_01.htm）
我的dfs就是犯了选取桥的错误。
白书上关于欧拉路的dfs是这样的

void Euler(int cnt)
{
    for(int i=0;i<n;i++)
    {
        if(!v[i]&&e[cnt].to==e[i].from)
        {
            v[i]=1;
            Euler(i);
            s[sp++]=i;
        }
    }
}

然后输出栈中的内容。这样很巧妙的做到了寻找欧拉路。
与一个结点相连的所有边都应该遍历到，所以不应该像我那样找到一条符合条件的边就退出循环。然后要知道遍历的顺序并不一定是最后欧拉路的顺序，因为在经过一个结点的时候，如果这个结点连接着多条边，那么必定经过某条边之后，还会回到这个结点，因为所有的边都必须遍历到，那么我们应该先经过这样的边，再去走其他的边；要找这样的边，就需要另一个dfs去验证经过这条边能否回到当前节点。而白书上的dfs巧妙在于先去寻找终点，再退回去寻找倒数第二个点，依次回溯，得到整个完整的欧拉路。