INDISET - Find all independent nodes
Let G be a graph with a set of n nodes and a set of m edges. An independent set I is a subset of nodes, no two nodes of which are connected by any edge in G.
A maximal independent set is an independent set such that adding any other node to the set forces the set to contain at least two nodes connected by an edge in G.
In this task, you are given a undirected graph as the input, and you have to find as many as possible independent nodes within the time limit. Your score is the total number of independent nodes found in all test cases.
Input
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.
Output
There should be one line output listing all valid independent nodes you found in the graph. The nodes are separated by one space.
Example
Input:
6 7
1 2
1 5
2 3
2 5
3 4
3 6
5 6
Output:
1 4 6
hide comments
smittal12:
2016-02-28 08:56:48
First I got 592 marks then 707 still leaderboard is showing 592...
|
|
Jimmy Tirtawangsa:
2012-08-26 09:15:19
Hi Tjandra salam kenal.
|
|
(Tjandra Satria Gunawan)(曾毅昆):
2012-07-11 09:42:54
Note: I know that Jimmy Tirtawangsa understand Indonesian language.
|
|
Nikolay Nedelchev:
2012-05-08 11:03:37
ok, 10x
|
|
Jimmy Tirtawangsa:
2012-05-08 00:39:45
No you can't, but it's somewhat correlated to the graph size. I set longer time limit for bigger graph.
|
|
Nikolay Nedelchev:
2012-05-07 18:32:05
And how do we know about which test case, which time limit is valid?
|
|
Jimmy Tirtawangsa:
2012-05-07 12:45:05
There are several datasets. Each is given its own time limit.
|
|
Nikolay Nedelchev:
2012-05-06 23:19:41
what means :
|
Added by: | Jimmy Tirtawangsa |
Date: | 2012-04-17 |
Time limit: | 0.200s-1.799s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 GAWK BASH BF |
Resource: | http://en.wikipedia.org/wiki/Independent_set_(graph_theory) |