INTSS  Internally Stable Sets
A weighted finite undirected graph is a triple G = (V, E, w) consisting of vertex set V, edge set , and vertex weighting function w such that and . For and , N(u) and N(K) will denote the neighboring vertex sets of u and K respectively, formally defined as:
A vertex set satisfying is called internally stable (also known as independent or anticlique). In this problem you must find an internally stable set B such that w(B) = max{w(S)}, where S belongs to the set of all internally stable sets of that graph.
Input
t – the number of test cases [t <= 100]
n k – [n – number of vertices (2 <= n <= 200), k – number of edges (1 <= k <= n*(n1)/2)]
then n numbers follows (wi  the weight of ith vertex) [ 0 <= wi <= 2^311]
then k pairs of numbers follows denoting the edge between the vertices (si sj edge between ith and jth verices) [1 <= si, sj <= n]
Output
For each test case output MaxWeight – the weight of a maximum internally stable set of the given graph. [ 0 <= MaxWeight <= 2^311]
Example
Input: 2 5 6 10 20 30 40 50 1 2 1 5 2 3 3 4 3 5 4 5 4 4 10 4 10 14 1 2 2 3 3 4 4 1 Output: 70 20
hide comments
gautams:
20150717 06:41:32
I have solved the problem but it is exceeding time limit. Please help. Do I have to know any specific thing in graph theory ?? 

Faisal Khan:
20130720 10:11:11
Last edit: 20130720 10:11:38 

Alex:
20130102 18:52:01
Isn't this an NPhard problem? 

Leonardo Lopez:
20121002 19:17:44
This is a tutorial exercise? 

[Trichromatic] XilinX:
20090413 03:07:17
Hard versions of this problem are MIS & MAXISET (Actually, both these two codes mean "Maximum Independent Set" :) 
Added by:  Roman Sol 
Date:  20041214 
Time limit:  21s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ERL JSRHINO NODEJS PERL6 VB.NET 
Resource:  ZCon 