hiho一下第五十周 (求欧拉路径)

http://hihocoder.com/contest/hiho50/problem/1

这题有重边,所以邻接矩阵用来统计节点u,v之间有多少条边相连,并且用另外一个数组统计每个节点的入度.

然后查找一个入度为奇数的点进行dfs(如果不存在就从n开始),

dfs的时候每次经过一条边就把这条边删除,因为一条边不会经过两次。

递归的时候保存路径.

总结起来:求解欧拉回路的方法就是,使用dfs,如果某条边被搜索到,则删除这条边,每次dfs结束之后,看当前节点还有没有与之相连的边,有就继续dfs下去.

最后,记录的回溯路径就是欧拉回路.

 #include <cstdio>

 #include <cstring>

 #include <vector>

 using namespace std;

 int p[],in[];

 int n,m,j;

 int g[][];

 void dfs(int x)

 {

     //printf("%d\n",x);

     for(int i=;i<=n;i++)

     {

         if(g[x][i])

         {

             //printf("%d\n",g[x][i]);

             int u=g[x][i];

             g[x][i]--;

             g[i][x]--;

             dfs(i);  //

         }

     }

     p[j++]=x;

 }

 int main()

 {

     //freopen("a.txt","r",stdin);

     int a,b,k;

     while(~scanf("%d%d",&n,&m))

     {

         memset(g,,sizeof(g));

         memset(in,,sizeof(in));

         for(int i=;i<m;i++)

         {

             scanf("%d%d",&a,&b);

             in[a]++;

             in[b]++;

             g[a][b]++;

             g[b][a]++;

         }

         memset(p,,sizeof(p));

         j=;

         for(int i=;i<=n;i++)

             if(in[i]&)

             {

                 k=i;

                 break;

             }

        // printf("%d\n",j);

         if(k<=n) dfs(k);

         else dfs(n);

         for(int i=;i<j-;i++)

             printf("%d ",p[i]);

         printf("%d\n",p[j-]);

     }

     return ;

 }

从别人看到了输入挂:

 #include <cstdio>

 int g[][]={},path[]={},N,M,u,v,i,pathsize=,start,deg[]={};

 char ch;

 void read(int &aa)

 {

     aa=;

     while(ch=getchar(),(ch<''||ch>'')&&(ch!='-'));

     while(ch>=''&&ch<='') {aa=(aa<<)+(aa<<)+ch-'';ch=getchar();}

 }

 void dfs(int b)

 {

     for(int i=;i<=N;++i) {

         if(i!=b&&g[b][i]) {

             --g[b][i],--g[i][b];

             dfs(i);

         }

     }

     ++pathsize;

     path[pathsize]=b;

 }

 int main()

 {

     read(N),read(M);

     for(;M--;) {

         read(u),read(v);

         ++g[u][v],++g[v][u];

         ++deg[u],++deg[v];

     }

     for(start=;start<=N;++start)

         if(deg[start]&)

             break;

     if(start<=N)

         dfs(start);

     else

         dfs(N);

     for(i=;path[i];++i) printf("%d ",path[i]);

 }

巴特西

hiho一下第五十周 (求欧拉路径)

最新文章

热门文章

巴特西

hiho一下 第五十周 (求欧拉路径)

最新文章

热门文章

hiho一下第五十周 (求欧拉路径)