Given a graph with n vertices (2 <= n <= 200). Find the largest set of vertices that each two vertices are connected.
Time: 1s, memory: 256MB
Input: First line contains two numbers n and k — the vertices and the edges.
Next k lines contains the k edges.
Output: The first line contain one number — The size of the set
The second line represents the vertices in the set. If there are more than one set that have the maximum size, print the set that is lexicographically smallest.
Example:
Input:
5 3
1 3
1 4
2 5
Output:
2
1 4
How can I solve this problem? Can you help me with this? Thank you!
How is your problem different from https://en.wikipedia.org/wiki/Clique_problem?
Is it solvable?
Sorry, I am lazy to read the entire thing.
No, it's NP-complete. Which is why I'm assuming they mean something different, and have to clarify.
Yeah actually the main problem is to give a set of points and a distance D, find the largest group of points that any two points have a distance no more than D.
I tried to convert it into a graph. Does that make the problem harder?
Yes, because in general graphs this problem is hard.
Can you provide me any other ways to approach this problem? Thank you!
So I'm just spitballing here without much thought. Assumptions: 1. 'Group of points all within distance D of themselves' <-> 'Group of points within a circle of diameter D' 2. An optimal placement of the circle on top of the points can always be shifted so that 2 points are on its edge
If they are true, something like this should work: Try all pairs of points to be on its edge. If you have a circle of known size and 2 points on its edge, you can determine the circle's location (exactly 2 possibilities). For both of them, check how many other points are within the circle.
Remember the best answer you come across over all pairs of outer points you try.
Perform depth first search to find all the connected( By u,v are connected I assume there is a path from u to v) components and the number of vertices in each connected component.
This gives the answer i think.
That'll come up to N^4 or N^5 I think.
Well first, I doubt the memory limit is 256GB (it's probably 256MB). Second, as Hodobox stated, this is the Clique problem which is NP-Hard, so you should probably clarify what the problem means.
Yes it is 256MB