SGU 156 Strange Graph

很有趣的一個題目

我們來一步一步分析此題

題目把點都分成兩種：

1. deg = 2的點 x type

2. deg > 2的點 y type

我們可以推知，如果有一個 y 型點，連到超過兩個 x 型點

這個圖就暴了。因為第三個 x 型點，不具有其中一個端點

既然被判掉了，我們就假設目前遭遇到的圖 y 型點都連到不超過兩個的 x 型點

接著可以知道，如果有一個 y 型點，連到剛好兩個 x 型點

這個 y 型點可以視為是一個 x 型點。因為他一定要從 x 型點進入，而如果是從其中一個 x 型點進來，他就必定是從另一個 x 型點出去

所以這種情形也被我們弄掉了，所以我們現在的圖 y 型點都連到剛好一個 x 型點

（題目有保證至少會連到一個）

接著，透過題目的另一個條件：

『對於一個 y 型點，連到他的所有 y 型點，他們之間都有相連』

你可以知道 y 型點都會互相相連，形成一個完全圖

而每一個人又剛剛好會向外連出一個 x 型點（如圖所示）

這是什麼意思呢？你會發現不管從哪邊進來都可以出去

而且走過每一個點就會走過每一個邊（不包括裡面的那些）

所以其實我們可以把中間那一坨看成一個點，而外面那些鏈狀物視為一條邊

並把原先要求的哈密頓迴路，轉換成歐拉迴路去求

（我的code不是這樣寫的，所以就不放了，雖然是AC的）