3423 . [模板題] Maximum Independent Set

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

Caido

User's AC Ratio

100.0% (2/2)

Submission's AC Ratio

100.0% (2/2)

Tags

library-checker template

Description

Given a simple undirected graph with $N$ vertices and $M$ edges. $i$-th edge is $(u_ i, v_ i)$。

Calculate the maximum independent set.

Input Format

$N$ $M$
$u_ 0$ $v_ 0$
$u_ 1$ $v_ 1$
:
$u_ {M - 1}$ $v_ {M - 1}$

Output Format

$X$
$p_ 0$ $p_ 1$ ... $p_ {X - 1}$

$X$ is the size of MIS, and $p_ i$ is the vertex index.

Sample Input 1

8 10
0 1
2 3
4 5
6 7
0 2
2 4
4 6
1 3
3 5
5 7

Sample Output 1

4
5 2 1 6

Sample Input 2

7 9
0 1
1 2
2 0
2 3
3 4
4 2
4 5
5 6
6 4

Sample Output 2

3
6 1 3

Hints

  • $1 \leq N \leq 40$
  • $0 \leq M \leq \frac{N(N-1)}{2}$
  • $0 \leq u_ i, v_ i < N$
  • $u_ i \neq v_ i$
  • $(u_ i, v_ i) \neq (u_ j, v_ j)$

Problem Source

library checker: maximum_independent_set

Subtasks

No. Testdata Range Score

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 5000 2097152 2097152
1 5000 2097152 2097152
2 5000 2097152 2097152
3 5000 2097152 2097152
4 5000 2097152 2097152
5 5000 2097152 2097152
6 5000 2097152 2097152
7 5000 2097152 2097152
8 5000 2097152 2097152
9 5000 2097152 2097152
10 5000 2097152 2097152
11 5000 2097152 2097152
12 5000 2097152 2097152
13 5000 2097152 2097152
14 5000 2097152 2097152
15 5000 2097152 2097152
Submit
Back to Top