欧拉回路-白红宇

欧拉回路

阅读量：4342 次

发布时间：2019-06-07

本文共 1412 字，大约阅读时间需要 4 分钟。

求欧拉回路dfs代码：

#include 
     
      #include 
      
       using namespace std;int n,m,dis[101],dis_=0,root=0x7fffffff,path[10001],now=0;bool map[101][101],ok=false,if_[101];void euler(int now,int gra){    path[gra]=now;    if(gra==m+1)    {        ok=true;        return ;    }    for(int i=1;i<=n;i++)    {        if(map[now][i])        {            map[now][i]=false;            map[i][now]=false;            euler(i,gra+1);            if(ok) return;            map[now][i]=true;            map[i][now]=true;        }    }}void euler_back(int now,int gra){    path[gra]=now;    if(gra==m+1)    {        if(now==root) ok=true;        return ;    }    for(int i=1;i<=n;i++)    {        if(map[now][i]&&!if_[i])        {            map[now][i]=false;            map[i][now]=false;            euler_back(i,gra+1);            if(ok) return;            map[i][now]=true;            map[now][i]=true;        }    }}int main(){    scanf("%d%d",&n,&m);    int from,to;    for(int i=1;i<=m;i++)    {        scanf("%d%d",&from,&to);        map[from][to]=true;        map[to][from]=true;        dis[from]++,dis[to]++;    }    for(int i=1;i<=n;i++)    {        if(dis[i]%2)        {            root=min(i,root);            dis_++;        }    }    if(dis_==2)    {        if_[root]=true;        euler(root,1);        if(ok)        {            cout<<"true 1"<

转载于:https://www.cnblogs.com/IUUUUUUUskyyy/p/6286710.html

你可能感兴趣的文章

My安卓知识6--关于把项目从androidstudio工程转成eclipse工程并导成jar包