1683 . 最大集團 The Largest Clique
TopCoder
Tags
Description
給你一張有向圖G（可能有自環或重邊），考慮以下轉換：
首先，建構一張新的圖T(G)，頂點集跟原圖G一樣。
在T(G)存在一條有向邊u→v若且唯若在G中存在一條u到v的路徑(path)。
符合這個條件的T(G)我們稱他是G的傳遞閉包(Transitive Closure)。
我們定義有向圖中的集團(Clique)是一個點集合U，
對任何集合內的兩個點u,v，必定存在一條u→v或v→u的有向邊。
集團的大小定義為這個集團的頂點個數。
現在給你一張圖G，請求出T(G)的最大集團大小。
Input Format
輸入的第一行包含一個正整數T表示測資筆數。
每筆測資的第一行包含兩個數字N, M，其中0 <= N <= 10,000、0 <= M <= 100,000。
N表示圖G中的頂點個數(編號1~N)、M表示圖G中的有向邊數。
接下來會有M行，每行兩個整數U, V，表示G中有一條U→V的有向邊。
Output Format
對每筆測資輸出一行包含一個數字K表示T(G)的最大集團大小。
Sample Input 1
1
5 5
1 2
2 3
3 1
4 1
5 2
5 5
1 2
2 3
3 1
4 1
5 2
Sample Output 1
4
Hints
2018/3/9 測資修正
Problem Source
原TIOJ1683 / UVa 11324 (測資範圍加大)
Subtasks
| No. | Testdata Range | Score |
|---|---|---|
| 1 | 0 | 33 |
| 2 | 1 | 33 |
| 3 | 2 | 34 |