首页 > 代码库 > UVA10054_The Necklace

UVA10054_The Necklace

2024-07-12 00:56:07   224人阅读

很简单，求欧拉回路。并且输出。

只重点说一下要用栈来控制输出。

为啥，如图：

如果不用栈，那么1->2->3->1就回来了，接着又输出4->5，发现这根本连接不上去，所以如果用栈的话，就会保存一条完整的路径咯。

因为是无向图，只要满足每个点的度数都是偶数的话就一定存在合法的欧拉回路了。

 

召唤代码君：

 

 

#include <iostream>#include <cstring>#include <cstdio>using namespace std;int a[51][51],n=50,d[51],m,T;void dfs(int x){    for (int i=1; i<=n; i++)        if (a[x][i])        {            a[x][i]--,a[i][x]--;            dfs(i);            printf("%d %d\n",i,x);        }}int main(){    int cas=0,U,V;    scanf("%d",&T);    while (T--)    {        memset(d,0,sizeof d);        memset(a,0,sizeof a);        scanf("%d",&m);        while (m--)        {            scanf("%d%d",&U,&V);            a[U][V]++,a[V][U]++;            d[U]++,d[V]++;        }        bool ans=true;        for (int i=1; i<=n; i++)            if (d[i]&1) ans=false;        if (cas) printf("\n");        printf("Case #%d\n",++cas);        if (!ans) printf("some beads may be lost\n");            else dfs(U);    }    return 0;}

　　


联系
我们