ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1182. Team Them Up!

Is my idea correct?
Posted by Roman Rubanenko 21 Oct 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?
Posted by Sergey Lazarev (MSU Tashkent) 21 Oct 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?
Posted by GastonFontenla 13 Aug 2015 02:33
Hi, I think that you should find the strongest connected components in a digraph.