Блог пользователя Firestone

Автор Firestone, история, 3 года назад, По-английски

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!

  • Проголосовать: нравится
  • +3
  • Проголосовать: не нравится

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +16 Проголосовать: не нравится

    Is it solvable?

    Sorry, I am lazy to read the entire thing.

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится +10 Проголосовать: не нравится

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

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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?

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Yes, because in general graphs this problem is hard.

      • »
        »
        »
        »
        3 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

        • »
          »
          »
          »
          »
          3 года назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          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.

»
3 года назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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.

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.