題目大意
給出兩個數字是一條邊,然後找出任意一個歐拉回路。
無向圖歐拉回路的條件:
1. 要聯通
2. 每個節點度必須是偶數
這個簡單題目卡了我一下午,結果就是少輸出了空行;
AC代碼
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int MX = +;
int m[MX][MX],IN[MX];
void init()
{
memset(IN,,sizeof IN);
memset(m,,sizeof m);
}
void dfs(int st)
{
for(int i=;i<=;i++) {
if(m[st][i]<=) continue;
m[st][i]--;m[i][st]--;
dfs(i);
printf("%d %d\n",i,st);
}
}
void solve(int st,int n)
{
for(int i=;i<=n;i++) {
if(IN[i]%==) continue;
puts("some beads may be lost");
return ;
}
for(int i=;i<=;i++)dfs(i);
}
int main()
{
int _;//freopen("in.txt","r",stdin);
scanf("%d",&_);
for(int cas=;cas<=_;cas++) {
int n,u,v,st;init();
scanf("%d",&n);
for(int i=;i<=n;i++) {
scanf("%d%d",&u,&v);
IN[u]++;IN[v]++;st = u;
m[v][u]++;m[u][v]++;
}
printf("Case #%d\n",cas);
solve(st,n);
puts("");
}
return ;
}