深圳布吉網(wǎng)站建設(shè)百度指數(shù)官網(wǎng)移動(dòng)版
這種「一筆畫」問題與歐拉圖或者半歐拉圖有著緊密的聯(lián)系，下面給出定義：
通過圖中所有邊恰好一次且行遍所有頂點(diǎn)的通路稱為 歐拉通路；
通過圖中所有邊恰好一次且行遍所有頂點(diǎn)的回路稱為 歐拉回路；
具有歐拉回路的無(wú)向圖稱為 歐拉圖；
具有歐拉通路但不具有歐拉回路的無(wú)向圖稱為 半歐拉圖。
對(duì)于無(wú)向圖 G，G 是歐拉圖當(dāng)且僅當(dāng) G 是連通的且沒有奇度頂點(diǎn)。
對(duì)于無(wú)向圖 G，G 是半歐拉圖當(dāng)且僅當(dāng) G 是連通的且 G 中恰有 0 個(gè)或 2 個(gè)奇度頂點(diǎn)。
對(duì)于有向圖 G，G 是歐拉圖當(dāng)且僅當(dāng) G 的所有頂點(diǎn)屬于同一個(gè)強(qiáng)連通分量且每個(gè)頂點(diǎn)的入度和出度相同。
對(duì)于有向圖 G，G 是半歐拉圖當(dāng)且僅當(dāng) 如果將 G 中的所有有向邊退化為無(wú)向邊時(shí)，那么 G 的所有頂點(diǎn)屬于同一個(gè)強(qiáng)連通分量；最多只有一個(gè)頂點(diǎn)的出度與入度差為 1；最多只有一個(gè)頂點(diǎn)的入度與出度差為 1；所有其他頂點(diǎn)的入度和出度相同。
2097. 合法重新排列數(shù)對(duì)
把數(shù)組 pairs 中出現(xiàn)的每個(gè) 數(shù) 看成一個(gè)節(jié)點(diǎn)，(start_i,end_i) 看成從 start_i 到 end_i 的一條有向邊，那么 pairs 的一個(gè)合法排列就對(duì)應(yīng)著一條路徑。這條路徑經(jīng)過了圖上的每一條邊恰好一次，是一條「歐拉通路」，因此目標(biāo)就是找出圖上的任意一條歐拉通路。
首先需要找到