V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
yangzhaofeng
V2EX  ›  算法

一道關於圖論的算法問題

  •  
  •   yangzhaofeng · 2020-02-19 00:21:14 +08:00 · 1378 次点击
    这是一个创建于 1723 天前的主题,其中的信息可能已经有所发展或是发生改变。

    定義單向邊:若節點 i 和 k 之間相連,則其間有i->kk->i兩條單向邊。現有 N 個節點和 E 條單向邊,其中N>=2E/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) 條路徑暫時還沒有頭緒。

    目前尚无回复
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   2998 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 41ms · UTC 13:32 · PVG 21:32 · LAX 05:32 · JFK 08:32
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.