ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

Обсуждение задачи 1182. Team Them Up!

Is my idea correct?
Послано Roman Rubanenko 21 окт 2010 00:24
Hi all.
I use dfs to find the number of connected components.
If there are 2 components,then i output each of them as a single team.If there is only 1 CC,then i output numbers from 1 to n/2  and from n/2+1 to n.
Otherwise "No solution".
It seems to me correct,but....
Or tell me some tests that prove my idea's fail)
Re: Is my idea correct?
Послано Sergey Lazarev (MSU Tashkent) 21 окт 2010 11:49
Your idea is incorrect.

1) If 1st person knows 2nd person it doesn't mean that 2nd person knows 1st person.
2) If 1st and 2nd persons know each other and 1st and 3rd persons also know each other it doesn't mean that 2nd person knows 3rd person and vice versa.

According to your algo in the first case both persons will be in one connected component, and in the second case all 3 persons will be in one connected component.
Re: Is my idea correct?
Послано GastonFontenla 13 авг 2015 02:33
Hi, I think that you should find the strongest connected components in a digraph.