UVa : 10608 (二)

解題的想法(失敗的，應該說，不太好的):

    這是我想了幾十個小時後得到的想法，雖然是失敗的，可是，它也為解決題目做了奠基，我是在這方法上做了改良才解出來的，所以，這想法的介紹還是必要的。

圖文無關，我只是想放 Starlight 而己

關系表:

    我把各個關系用一個二維的陣列來記錄，把所有的關系用一個矩陣來代表，為了說明的方便，我拿測資的第一筆來做解譯，它 N = 3 ，M = 2。

    陣列內的元素一開始都是 0，如果有相對應的關系才會設成 1，這邊的行跟列都是從 1 開始的，代表不同的人，要注意我們的陣列是從編號 0 開始的，所以，如果要存取 row 1 column 3 的值，是要 陣列[0][2]。

    首先，3 與 2 有關系，所以要把 row 3 column 2 那格設成 1 ，而且也要把 row 2 column 3 設成 1 ，因為 關系是雙向的，如果不把 row 2 column 設成 1 ，之後程式在跑會出錯。把所有輸入的結果都存好後，會變成下面那樣。

    接著，就可以開始來找出各個群了。

如何找尋關係:

    之後做的就是查表的工作了。

關系表

    透過關系表來查找，我們會一列一列的找，拿第 1 列來說，由第 1 列往下找，可以找到跟 1 有關系的其他數字，由第 2 列往下找，可以找到跟 2 有關系的其他數字.... 。

    那... 要怎麼把那些有相同人的群結合在一起，找出最大群有多少人呢 ? 我是使用遞迴的方式來解決的，假設我有寫了一個函式 F，它的作用是這樣，輸入一個值 N ，然後它會在第 N 列下，一個一個找 ，如果有找到 1 的話，那就把找到 1 元素的那行，行當為 N ，再次呼叫 F ，遞迴做下去。

    以下為圖解
    

    如此遞迴做下去，找到所有相關的關系，不過，會有一個問題，我們接續上一張來解譯，會發生什麼問題。

    有發現嗎 ? 這樣做下去會沒完沒了的，所以，我們在發現關係後，要把那關係歸零。

    依此做下去， F2 會在 col 2 發現 2 與 1 有關系，把 row 1 col 2 那行設成 0 ，呼叫 F3 找尋 col 1 下的關系 (因為 col 1 的元素都是 0 了，所以 F3 不會再呼叫 F 函式了)，F3 做完後，程式回到 F2 ，再找往下找關係，依此做下去，最後，等 F1 跑到 col 1 的最後一個 row 的時候，我們就把所有跟 1 有關係的元素都看過一次了。

    假如 F1 在 col 2 有找到關係的話，它會是跟 F1 在 col 1 下找到的關係是不同的群組，不過，在這範例裡，F1 在 col 2 執行時，關係都沒了 (因為 F1 在 col 1 執行時，所有的關係都被它給拿走了)，所以，也就沒有其它的群了，不過，程式還是會執行到最後。

    可以看出，這種方法可以找到所有衍伸的關係，還有分群的效果 (有感覺出來嗎 ?)。

    下篇，我會介紹，如何找出最大的一群。

後記:

    幹.... ，第二篇拖了好久才生出來，雖然說我上禮拜是期中考啦，不過，最近真的是沒有什麼心情寫那些教學文章，只想單純的學習東西而己。寫文章真的是有點累人，而且.... ，馬的，這一個教學文章有夠難打的，很多東西我都不知道要怎麼表達，自己的邏輯要說明清楚真的有夠難的。

    希望讀者可以看得懂我想表達什麼...... (我表達能力不好，但我盡力了)。