TopCoder

User's AC Ratio

78.6% (11/14)

Submission's AC Ratio

52.3% (81/155)

Tags

Description

在圖論中,一個大小為 $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);
}

Input Format

輸入首行有兩個整數 $N, M$,代表點的個數以及邊的個數。

接下來 $M$ 行,第 $i$ 行有兩個整數 $a_i, b_i$,代表第 $i$ 條邊連接著點 $a_i$ 和點 $b_i$。

  • $1 \leq N \leq 100$
  • $0 \leq M \leq \frac{N(N + 1)}{2}$
  • $1 \leq a_i, b_i \leq N$
  • 保證給定的圖為一般簡單圖,意即沒有重邊和自環
  • 保證所有測試資料都是按照題目敘述中的程式產生

Output Format

輸出一個數字於一行,代表最大團的點數量。

Sample Input 1

4 5
2 3
2 4
1 3
3 4
1 2

Sample Output 1

3

Hints

Problem Source

Subtasks

No. Testdata Range Constraints Score
1 0 範例測資。 0
2 0~6 無特別限制。 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 262144 65536 1 2
1 1000 262144 65536 2
2 1000 262144 65536 2
3 1000 262144 65536 2
4 1000 262144 65536 2
5 1000 262144 65536 2
6 1000 262144 65536 2