定義單向邊:若節點 i 和 k 之間相連,則其間有i->k
和k->i
兩條單向邊。現有 N 個節點和 E 條單向邊,其中N>=2
且E/2>=1
。
定義路徑的加法:若一條路徑i->...->j
的尾和另一條路徑j->...->k
的首相同,則i->path_p->j + j->path_q->k = i->path_p->j->path_q->k
定義路徑的減法:i->path_p->j->path_q->k - i->path_p->j = j->path_q->k
其中 i->path_p->j != -(j->reverse_path_p->i)
定義環路:從某個節點出發經過若干個節點之後回到出發節點的路徑。
定義獨立環路集:該集合中的每一條環路都無法用該集合中的其他環路線性組合而成,但圖中的任意一條環路均可由該集合中的獨立環路線性組合(其中線性組合的係數為 1,0 或-1 )而成。
易得一個獨立環路集中獨立環路的數量為 E-(N-1)。輸入節點及其連接狀況,求一個可行的獨立環路集。
輸入:
第一行為 偶數 E 和 自然數 N
接下來的 E/2 行為連接情況。均為雙向連接。
輸出:
E-(N-1)行,為一個可行的獨立環路集
Example input 1:
6 3
1 2
2 3
1 3
Example output 1:
1 2 1
2 3 2
3 1 3
1 2 3 1
Example input 2:
12 5
1 2
2 3
3 4
4 5
5 1
1 3
Example output 2:
1 2 1
2 3 2
3 4 3
4 5 4
5 1 5
1 3 1
1 2 3 1
1 3 4 5 1
兩個 example 的圖如下
https://i.loli.net/2020/02/19/HKEqvitX8UcAlxP.png
我個人目前是知道先打印所有 i->j->i
的 E/2 條路徑的,但是剩下的 E/2-(N-1) 條路徑暫時還沒有頭緒。