The Necklace 【UVA - 10054】【欧拉回路】

题目链接


  一道欧拉回路的经典问题!

  题意:有N条边,我们要用这N条边首尾相接的拼接成一个环,也就是相同颜色可以相互链接,问他们能不能构成一个环?并且按照你的欧拉回路跑的顺序去输出这N条边的排列(SPJ)。

  思路:很明显的就是一个欧拉回路问题了,但是不要忘记判断它本身是一个连通图的问题,所以要用并查集维护一下,其次呢,要看看有没有点的度为奇数,如果有奇数的话,那么就GG了,是构不成欧拉回路的。然后就是一个dfs+栈维护的过程了。期间我忘记我离散化了,以此WA了不计其数。难受哇……

#include <iostream>
#include <cstdio>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
#include <limits>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <bitset>
//#include <unordered_map>
//#include <unordered_set>
#define lowbit(x) ( x&(-x) )
#define pi 3.141592653589793
#define e 2.718281828459045
#define INF 0x3f3f3f3f3f3f3f3f
//#define INF 10000007.
#define eps 1e-7
#define HalF (l + r)>>1
#define lsn rt<<1
#define rsn rt<<1|1
#define Lson lsn, l, mid
#define Rson rsn, mid+1, r
#define QL Lson, ql, qr
#define QR Rson, ql, qr
#define myself rt, l, r
#define MP(a, b) make_pair(a, b)
using namespace std;
typedef unsigned long long ull;
typedef unsigned int uit;
typedef long long ll;
const int maxN = 1005;
int N, _UP, lsan[maxN << 1], len, du[55], root[55];
int fid(int x) { return x == root[x] ? x : root[x] = fid(root[x]); }    //要看联通块的个数是否为1
struct In_put
{
    int a, b;
    In_put(int a=0, int b=0):a(a), b(b) {}
    inline void IN() { scanf("%d%d", &a, &b); }
}t[maxN];
int mp[55][55];
int Stap[maxN << 1], Stop;
void dfs(int u)
{
    for(int i=1; i<=_UP; i++)
    {
        while(mp[u][i])
        {
            mp[u][i]--; mp[i][u]--;
            dfs(i);
        }
    }
    Stap[++Stop] = u;
}
int main()
{
    int T; scanf("%d", &T);
    for(int Cas = 1; Cas <= T; Cas++)
    {
        if(Cas ^ 1) printf("\n");
        scanf("%d", &N);
        len = 0;
        for(int i=1; i<=N; i++)
        {
            t[i].IN();
            lsan[++len] = t[i].a; lsan[++len] = t[i].b;
        }
        sort(lsan + 1, lsan + len + 1);
        _UP = (int)(unique(lsan + 1, lsan + len + 1) - lsan - 1);
        for(int i=1; i<=_UP; i++) { du[i] = 0; root[i] = i; }
        for(int i=1, u, v; i<=N; i++)
        {
            t[i].a = (int)(lower_bound(lsan + 1, lsan + _UP + 1, t[i].a) - lsan);
            t[i].b = (int)(lower_bound(lsan + 1, lsan + _UP + 1, t[i].b) - lsan);
            du[t[i].a]++; du[t[i].b]++;
            u = fid(t[i].a); v = fid(t[i].b);
            if(u ^ v) root[u] = v;
        }
        bool ok = true;
        for(int i=1; i<=_UP; i++) if(du[i] & 1) { ok = false; break; }
        if(ok)
        {
            int cnt = 0;
            for(int i=1; i<=_UP; i++)
            {
                cnt += fid(i) == i;
            }
            if(cnt > 1) ok = false;
        }
        printf("Case #%d\n", Cas);
        if(!ok) { printf("some beads may be lost\n"); continue; }
        for(int i=1; i<=_UP; i++) for(int j=1; j<=_UP; j++) mp[i][j] = 0;
        Stop = 0;
        for(int i=1; i<=N; i++)
        {
            mp[t[i].a][t[i].b]++;
            mp[t[i].b][t[i].a]++;
        }
        dfs(1);
        for(int i=Stop; i>1; i--) printf("%d %d\n", lsan[Stap[i]], lsan[Stap[i - 1]]);
    }
    return 0;
}

 

The Necklace 【UVA - 10054】【欧拉回路】The Necklace 【UVA - 10054】【欧拉回路】 Andres_Lionel 发布了730 篇原创文章 · 获赞 900 · 访问量 8万+ 他的留言板 关注
上一篇:Exchange UVA - 1598


下一篇:UVA 10006 Carmichael Numbers