Firestone's blog

I need some help...
By Firestone, history, 3 years ago, In English

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!

  • Vote: I like it
  • +3
  • Vote: I do not like it

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How is your problem different from https://en.wikipedia.org/wiki/Clique_problem?

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +16 Vote: I do not like it

    Is it solvable?

    Sorry, I am lazy to read the entire thing.

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +10 Vote: I do not like it

      No, it's NP-complete. Which is why I'm assuming they mean something different, and have to clarify.

      → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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?

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yes, because in general graphs this problem is hard.

      → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Can you provide me any other ways to approach this problem? Thank you!

        → Reply
        • »
          »
          »
          »
          »
          3 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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.

          → Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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.

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply