【題目鏈接】

ybt 1375：騎馬修柵欄(fence)
洛谷 P2731 [USACO3.3]騎馬修柵欄 Riding the Fences

【題目考點】

1. 圖論：歐拉回路

• 歐拉回路存在的條件：圖中所有頂點的度都是偶數(shù)
• 歐拉路徑存在的條件：圖中只有兩個度為奇數(shù)的頂點。而且這兩個頂點是歐拉路徑的起點與終點。

求解歐拉回路使用Hierholzer算法
復(fù)雜度：$O(V+E)$

【解題思路】

該圖是無向圖，頂點就是圖中的頂點，柵欄是邊。
“柵欄都是連通的”，意味著這是一個無向連通圖。
“使每個柵欄都恰好被經(jīng)過一次”，就是每條邊都經(jīng)過一次。該問題為求歐拉路徑?？梢允褂肏ierholzer算法解決。
“兩頂點間可能有多個柵欄”意味著可能有重邊，但Hierholzer算法可以處理有重邊或自環(huán)的圖。
“輸出500進制表示法中最小的一個”，即為輸出字典序最小的歐拉路徑頂點序列。
只需要在實現(xiàn)Hierholzer算法時，包括選擇起始頂點或某頂點的鄰接點時，盡量選擇編號較小的頂點來訪問即可。

在輸入邊時，統(tǒng)計頂點編號的最大值，作為總頂點數(shù)量。

首先從小到大遍歷所有頂點

• 如果存在奇數(shù)度的頂點，選擇該頂點作為起始點。
• 如果不存在奇數(shù)度的頂點，那么所有頂點的度都是偶數(shù)，任選頂點作為起始點。這里選擇1號頂點為起始點。

從起始頂點出發(fā)，進行深搜，使用Hierholzer算法求歐拉路徑。為了滿足條件，必須按頂點編號從小到大訪問一個頂點的所有鄰接點。

可以使用鄰接矩陣或鄰接表完成該題。文章來源地址http://www.zghlxwxcb.cn/news/detail-477713.html

【題解代碼】

解法1：鄰接矩陣

#include<bits/stdc++.h>
using namespace std;
#define N 505
int edge[N][N], n, m, deg[N];//n:頂點數(shù) m:邊數(shù) deg[i]:頂點i的度
stack<int> stk;
void dfs(int u)//Hierholzer算法 
{
    for(int v = 1; v <= n; ++v)
    {
        if(edge[u][v])
        {
            edge[u][v]--;
            edge[v][u]--;
            dfs(v);
        }
    }
    stk.push(u);
}
int main()
{
    int f, t, st = 1;//st:起點 
    cin >> m;
    for(int i = 1; i <= m; ++i)
    {
        cin >> f >> t;
        n = max(n, max(f, t));
        edge[f][t]++;
        edge[t][f]++;
        deg[f]++;
        deg[t]++;
    }
    for(int v = 1; v <= n; ++v)//如果找到奇數(shù)度頂點，就從奇數(shù)度頂點出發(fā)，否則從1出發(fā) 
    {
        if(deg[v] % 2 == 1)
        {
            st = v;
            break;
        }
    }
    dfs(st);
    while(stk.empty() == false)
    {
        cout << stk.top() << endl;
        stk.pop();
    }
    return 0;
}

解法2：鄰接表

#include<bits/stdc++.h>
using namespace std;
#define N 505
#define M 1050
struct Node
{
	int v, e;//v：頂點 e：邊編號 
	Node(){}
	Node(int a, int b):v(a), e(b){}
};
int n, m, beg[N], deg[N];//n:頂點數(shù) m:邊數(shù) deg[i]:頂點i的度 beg[i]:頂點i的鄰接點從edge[i][beg[i]]開始 
bool vis[M];//vis[i]：邊i是否已訪問過 
vector<Node> g[N];
stack<int> stk;
bool cmp(Node a, Node b)
{
	return a.v < b.v;
}
void dfs(int u)//Hierholzer算法 
{
    for(int &i = beg[u]; i < g[u].size(); ++i)
    {
    	int v = g[u][i].v, e = g[u][i].e;
        if(vis[e] == false)
        {
            vis[e] = true;
            dfs(v);
        }
    }
    stk.push(u);
}
int main()
{
    int f, t, st = 1;//st:起點 
    cin >> m;
    for(int i = 1; i <= m; ++i)
    {
        cin >> f >> t;
        n = max(n, max(f, t));
        g[f].push_back(Node(t, i));
        g[t].push_back(Node(f, i));
        deg[f]++;
        deg[t]++;
    }
    for(int v = 1; v <= n; ++v)
    	sort(g[v].begin(), g[v].end(), cmp);
    for(int v = 1; v <= n; ++v)
    {//如果找到奇數(shù)度頂點，就從奇數(shù)度頂點出發(fā)，否則從1出發(fā) 
        if(deg[v] % 2 == 1)
        {
            st = v;
            break;
        }
    }
    dfs(st);
    while(stk.empty() == false)
    {
        cout << stk.top() << endl;
        stk.pop();
    }
    return 0;
}

到了這里，關(guān)于信息學(xué)奧賽一本通 1375：騎馬修柵欄(fence) | 洛谷 P2731 [USACO3.3]騎馬修柵欄 Riding the Fences的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！