在圖論中,一個大小為 $N$ 的「團」代表一張有 $N$ 個節點的無向圖,滿足任意兩點之間都恰有一條邊。
現在給你一張 $N$ 點 $M$ 邊的一般簡單無向圖,你請找出點最多的子圖滿足他是一個團,這樣的子圖又被稱為「最大團」。
以下是系統用來生成無向圖的程式:
#include "testlib.h"
#include <vector>
#include <utility>
using namespace std;
int main(int argc, char* argv[]) {
registerGen(argc, argv, 1);
int n = atoi(argv[1]);
int m = atoi(argv[2]);
vector<pair<int, int>> edges;
for (int i = 1; i <= n; ++i)
for (int j = i + 1; j <= n; ++j)
edges.emplace_back(i, j);
shuffle(edges.begin(), edges.end());
edges.resize(m);
printf("%d %d\n", n, m);
for (auto [a, b] : edges)
if (rnd.next(0, 1))
printf("%d %d\n", a, b);
else
printf("%d %d\n", b, a);
}
輸入首行有兩個整數 $N, M$,代表點的個數以及邊的個數。
接下來 $M$ 行,第 $i$ 行有兩個整數 $a_i, b_i$,代表第 $i$ 條邊連接著點 $a_i$ 和點 $b_i$。
輸出一個數字於一行,代表最大團的點數量。
No. | Testdata Range | Constraints | Score |
---|---|---|---|
1 | 0 | 範例測資。 | 0 |
2 | 0~6 | 無特別限制。 | 100 |