### gogateiiit's blog

By gogateiiit, history, 4 months ago, ,

Can anyone help me solve below problem?

Given an array with N numbers and given list of pair of integers u and v where each entry is two indices which cannot be together in chosen subset.Tell maximum possible size of such subset.

Don't worry about constraints tell your best solution.

 » 4 months ago, # |   0 Maximum independent set. Polynomial (even linear) in some graphs.
•  » » 4 months ago, # ^ |   0 Thanks AlexandruValeanu for the reference,Original problem which I simplified to above problem was given array with N numbers find subset such that product of any two numbers in subset is not cube. 1<=N<=100 and number in 1<=array<=1000000 and 1 is cube. Any thoughts on how to solve it.
•  » » » 4 months ago, # ^ | ← Rev. 2 →   +3 I think it's a bipartite graph, so Max independent set problem can be solved by creating the flow network and getting the max flow, so the answer to the problem is: Ans = TotalNodesNumber - MaxFlow
•  » » » » 4 months ago, # ^ |   0 Can subset contain a cube? If it is so final graph can contain one clique of cubes in addition to bipartite part.