一道關於圖論的算法問題

[yangzhaofeng]

定義單向邊：若節點 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) 條路徑暫時還沒有頭緒。