【題目鏈接】

ybt 1341：【例題】一筆畫問題

【題目考點】

1. 圖論：歐拉回路

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

【解題思路】

• 無向圖有歐拉回路的條件：所有頂點的度都是偶數(shù)。
• 無向圖有歐拉路徑的條件：有兩個頂點的度是奇數(shù)，其余頂點的度都是偶數(shù)。

該題默認(rèn)一定有歐拉路徑或歐拉回路。
遍歷選擇起始頂點，如果v的度為奇數(shù)，那么選擇該頂點為起始頂點。否則起始頂點默認(rèn)為1號頂點。
使用Hierholzer算法可以在$O(V+E)$的時間復(fù)雜度內(nèi)求出歐拉回路。
頂點數(shù)n最大為100，可以使用鄰接矩陣或鄰接表解決。文章來源地址http://www.zghlxwxcb.cn/news/detail-639804.html

【題解代碼】

解法1：鄰接矩陣

#include<bits/stdc++.h>
using namespace std;
#define N 105
int n, m, edge[N][N], 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] = 0;
            dfs(v);        
        }
    }
    stk.push(u);
}
int main()
{
    int st = 1, f, t;//st:起點 
    cin >> n >> m;
    for(int i = 1; i <= m; ++i)
    {
        cin >> f >> t;
        edge[f][t] = edge[t][f] = 1;
        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() << ' ';
        stk.pop();
    }
    return 0;
}

解法2：鄰接表

#include<bits/stdc++.h>
using namespace std;
#define N 105
#define M 2005
struct Node
{
	int v, e;//v:頂點編號 e：邊的編號 
	Node(){}
	Node(int a, int b):v(a), e(b){}
};
int n, m, deg[N], beg[N];//n:頂點數(shù) m:邊數(shù) deg[i]:頂點i的度 beg[i]：頂點i的鄰接點從edge[beg[i]]開始算起，前面的相當(dāng)于刪掉了。 
vector<Node> edge[N];
bool vis[M];
stack<int> stk;
void dfs(int u)//Hierholzer算法 
{
	for(int &i = beg[u]; i < edge[u].size(); ++i)//i是beg[u]的引用，++i相當(dāng)于++beg[u]，這樣在下一次訪問頂點u的鄰接點時，只需要從下標(biāo)beg[u]開始看起，前面的當(dāng)做已經(jīng)被刪掉了
	{
		int v = edge[u][i].v, e = edge[u][i].e;
		if(vis[e] == false)
		{
			vis[e] = true;
			dfs(v);
		}
	}
    stk.push(u);
}
int main()
{
    int st = 1, f, t;//st:起點 
    cin >> n >> m;
    for(int i = 1; i <= m; ++i)
    {
        cin >> f >> t;
        edge[f].push_back(Node(t, i));
        edge[t].push_back(Node(f, i));
        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() << ' ';
        stk.pop();
    }
    return 0;
}

到了這里，關(guān)于信息學(xué)奧賽一本通 1341：【例題】一筆畫問題的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！