NOTINDY - Few to cover

no tags 

Let G be a graph with a set of n nodes and a set of  m edges. A vertex cover set VC is a subset of nodes, such that all edges in G have at least one of their end points in VC.

A minimal vertex cover set is a vertex cover set such that removing any vertex from the set will make at least one edge in G left uncovered.

In this task, you are given a undirected graph as the input, and you have to find as small as possible vertex cover set within the time limit. Your score is the total number of vertex cover nodes found in all test cases.


The first line contains two integers, n and m, representing the numbers of nodes and edges in the graph. 3  ≤ n ≤ 2000 and 3 ≤ m ≤ 40000. The nodes are numbered 1..n, but not necessarily in any order. The next m lines contain pair of integers representing edges between two nodes. The list of edges are not in any particular order.


There should be one line output listing all valid minimal set vertex cover nodes you found in the graph. The nodes are separated by one space.


6 7
1 2
1 5
2 3
2 5
3 4
3 6
5 6 Output: 2 3 5

Added by:Jimmy Tirtawangsa
Time limit:0.100s-1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)