Maximum Independent Set

View as PDF

Submit solution

Points: 15
Time limit: 2.0s
Memory limit: 128M

Problem type

Given a simple undirected graph with N vertices numbered 0 to N-1 and M edges. i-th edge is (u_i,v_i).

Calculate the maximum independent set.

The maximum independent set is the largest subset of nodes in the graph such that no nodes in the subset are connected by any edge in the original graph.


1\le N\le 40

0\le M\le \frac{N(N-1)}2

0\le u_i,v_i<N

u_i\ne v_i

(u_i,v_i)\ne(u_j,v_j) when i\ne j

Input Specification

The first line contains two integers N and M.

The next M lines each contain two integers: u_i and v_i, denoting an edge between u_i and v_i.

Output Specification

The first line contains an integer X, the size of the largest independent set.

The next line contains X integers, the nodes in an maximum independent set.

Sample Input

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

Sample Output

5 2 1 6


There are no comments at the moment.