#include 
     
      #include 
      
       #include 
       
        using namespace std;int g[111][111];int cnt[111];stack
        
          st;int n,m;//搜索求欧拉回路或欧拉通路void dfs(int u, int t){    st.push(u);    int k = 0;    for(int i=n; i>=t; --i)    {        if(g[u][i]>0)        {            k = 1;            g[u][i] = g[i][u] = 0;            dfs(i,1);            break;        }    }    if(k==0)//如果是桥，说明要回溯    {        st.pop();        int x = st.top();        g[u][x] = g[x][u] = 1;        int a = u + 1;//下一条边继续搜索        if(st.size()!=m)        {            st.pop();            dfs(u,a);        }        else//如果结点数==边数，则表明搜索的结果刚好是回路或者通路            st.push(u);    }}int main(){    int i,u,v;    scanf("%d%d",&n,&m);    for(i=0; i
        
       
      
     

http://acm.fafu.edu.cn/problem.php?id=1006

欧拉回路中是不存在桥的，因为一个边进去，肯定有一条边出来，这是欧拉回路的性质

所以可以 

1 void dfs(int u) 2 { 3      4     for(int i=1;i<=n;++i) 5     { 6         if(g[u][i]!=0) 7         {     8             g[u][i]-=1; 9             g[i][u]-=1;10             dfs(i);11             path[cnt++] = u;12             13         }14     }15 }

求欧拉路径的时候才需要注意桥，因为如果不是最后一步的时候走桥，那么走桥之后，就不能回来了。

 

 

 

 

单词游戏

有个盘子，每个盘子上写着一个仅由小写字母组成的英文单词。你需要给这

N些盘子安排一个合适的顺序，使得相邻两个盘子中，前一个盘子上面单词的末字母等于后一个盘子上面单词的首字母。

请你编写一个程序，判断是否能达到这一要求。如果能，请给出一个合适的顺序。

想法1：如果盘子A的末字母等于盘子B的首字母，那么盘子A到盘子B连一条有向边。

那么问题就转化为如何走遍所有的顶点且每个顶点仅访问一遍。即哈密顿路径。这是不好求的。

想法2：如果盘子A的首字母是a，末字母是c，那么a与c之间有一条有向边，那么问题就转化为了欧拉路径。

想法1是用顶点表示元素，边表示关系。这是很正常的思想。

想法2是用边表示元素，而顶点表示关系，是逆向思维。需要好好锻炼。