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

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

Problem : You are given a connected graph with N nodes and M edges, graph does not contain multiple edges and self loops. An independent set of nodes is the set in which no two nodes are connected to each other. You need to find the largest independent set.

Constraints : 3 <= N <= 1e5 and (N — 1) <= M <= 2e5

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

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

It is NP-hard problem in general.