PROBLEM LINKSDIFFICULTYSIMPLE PREREQUISITESGraph Theory, Union Find, Depth First Search PROBLEMAn Office has several people on which a relationship of being mutual friends is defined. Two people who are friends will always choose to accompany each other while escaping from fire. Under these conditions, what are the maximum number of escape routes may be built such that none of them may be empty. Also, each set of people who escape together, must have a captain assigned. Count the number of ways of assigning captains. QUICK EXPLANATIONLet us define a graph whose vertices are people. An undirected edge connects two people who are friends. On this graph, two vertices will be of the same color if they share an edge. This represents that the two people should have to go in the same fire escape route. We wish to maximize the number of colors used. All the vertices in a connected component in this graph will have to be in the same color. The above is easy to see because
This observation leads us to the following The maximum number of fire escape routes that may be built is equal to the number of connected components. The second part of the problem  Finding the ways to assign captains  is equal to the product of the number of vertices in each connected component. This can be derived by simple permutation / combination. (Since we need exactly 1 member from each set, the answer must be the product of the cardinality of the sets). EXPLANATIONThe number of connected components can be found by use of either of the following techniques Depth First SearchSince this is an undirected graph, the number of times a Depth First Search starts from an unvisited vertex is equal to the number of connected components. We would like to store the graph as an adjacency list due to the large number of vertices (the number of edges are not too many). Lets look at dfs implementation in pseudocode. Both the Setter's and Tester's coe use DFS to solve the problem. for u = 1 to N if u is not visited connected_components++ dfs(u) dfs(u) mark_visited(u) for all children v, of u if v is not visited dfs(v) Union FindUnion Find or Disjoint Set Data structures allow you to merge two sets of items together dynamically and maintain for each item  to which set does it belongs. You can consume a Union Find data structure to join each pair of friends. At the end of this, just count the number of distinct components to get the answer. for u = 1 to N initializenewsetwith1item(u) for e = 1 to M /* all edges */ joinsets( e.first, e.second ) Let cc = Array of size N for u = 1 to N cc[ findsetroot(u) ]++ for u = 1 to N if cc[u] > 0 connected_components++ There is one detail missing from the above two approaches. Handling of part 2 of the question. We wish to find the number of items in each connected component and find the product of these numbers.
SETTER'S SOLUTIONCan be found here. TESTER'S SOLUTIONCan be found here.
This question is marked "community wiki".
asked 12 Mar '13, 06:04

Please help . Getting Wrong answers for even test case!!! link to my code > http://ideone.com/lU40Sl answered 19 May '13, 18:53

i have used same approach as gven in editorial but it is giving me wrong answer.anyone explain me....where i am wrong first in C is C SOLUTION http://www.codechef.com/viewsolution/1910690 and second is in JAVA is JAVA SOLUTION http://www.codechef.com/viewsolution/1907414 answered 13 Mar '13, 20:23
They both have the same mistake. You do not handle possible overflow in this statement total = ((total % N)*(count % N) % N; As you can see, because N is 1000000007, the result of the product might exceed the range of 32bit integers. You must cast total as long long in C to solve the issue. Cast total to long in JAVA to get AC.
(15 Mar '13, 19:23)
Yes right... after changing the logic to total = ((total % N)*(count % N) % N;.. my code also worded.. huh.. http://www.codechef.com/viewsolution/1927944
(16 Mar '13, 00:54)

If you're having a problem with StackOverflow on Java, use BFS instead of DFS. I had a problem with DFS and my switch over fixed it. answered 12 Mar '13, 08:32

Once i did the setunion of all given edges, i did a findset (with pathcompression) on all vertices. Now, the number of distinct set representatives gives the number of connected components. We can also get the cardinality of each set from this information. http://www.codechef.com/viewsolution/1871116 answered 12 Mar '13, 12:36

@gamabunta @tijoforyou Are you sure implementing with DFS would pass all test cases without TLE. Initially I did it with DFS but was getting TLE. Then I did it with disjoint sets. Yet again I got a TLE with a simple implementation of union. But when I changed my implementation to Union by Rank, I got an AC with a runtime of 1.02 sec. http://www.codechef.com/viewsolution/1894308 answered 12 Mar '13, 13:35

Running DFS is getting TLE. Why? Check my submissions: http://www.codechef.com/viewplaintext/1881613 answered 12 Mar '13, 15:16
You have loop
(12 Mar '13, 16:18)
@anton_lunyov >> So, if I consider the case of graph consisting of no edges separately, will it run within TL?
(12 Mar '13, 16:29)
(12 Mar '13, 16:34)
No. The graph could have many components, say 90000, and you still will get TLE. Also why you are creating the array
(12 Mar '13, 16:48)
and that is why my code was 270M :(
(12 Mar '13, 17:04)
@anton_lunyov >> can you give some large test files, like you did for CHEFHACK?
(12 Mar '13, 17:06)
showing 5 of 6
show all

Need help finding bug in my solution http://www.codechef.com/viewplaintext/1933093. Was getting WA :( answered 12 Mar '13, 18:04

I got accepted using BFS using queues....but the same code I tried to implement it with DFS using stacks it gave TLE...whereas the recursive version of DFS got AC.could you tell me the reason for the TLE...was my code going into infinite loop or just didn't achieve the desired time limit. TLE CODE: http://www.codechef.com/viewplaintext/1901407 AC CODE: http://www.codechef.com/viewplaintext/1889867 Thanks in advance. answered 12 Mar '13, 18:47

I need help finding bug in my solution. I use Union Find to solve this problem in Java, and was getting a WA. http://www.codechef.com/viewsolution/1937788 Thanks. answered 13 Mar '13, 02:48
Checkout the fixes here. I could point out two bugs
(15 Mar '13, 19:45)

can you tell me where my solution is failing? my submission is http://www.codechef.com/viewsolution/1909473 answered 13 Mar '13, 14:50

Can anyone tell me what is wrong with my approach and for which test case it fails..... My submission id is http://www.codechef.com/viewsolution/1913075 answered 13 Mar '13, 19:34

Hi all, I dont know how to represent graph having large no of nodes to represent using adjacency list. I know it requires hash table(as using linked list is not feasible here) but i want to know how to implement. answered 13 Mar '13, 20:25
This might help, https://class.coursera.org/algs4partI002/lecture/8
(14 Mar '13, 00:55)

I am getting wrong answer ......... Can you give me failing case..... http://www.codechef.com/viewsolution/1930220 answered 13 Mar '13, 22:07

I have used BFS instead of DFS but am getting a wrong answer. Could you please point out the mistake? answered 17 Mar '13, 11:22
Hey, am still getting WA. Can you give me any border test case? http://www.codechef.com/viewsolution/1954203
(21 Mar '13, 12:04)

Hi, i used the Union Set Method , but for some reason it kept flagging it as Wrong Answer. I wrote a solution in C first, but thought that might be overflowing for some value, so i resorted to Python, in which overflowing will not be an issue, given the range. My solution is here : http://www.codechef.com/viewsolution/1908378 (PYTH) Can anyone tell me where it's going wrong ? Thanks. I'm all out of ideas. answered 17 Mar '13, 20:33

http://www.codechef.com/viewsolution/1892955 please tell me in which cases my code is getting WA.......... answered 18 Mar '13, 15:36

please give me a case where my code gives wrong answer. I have used a different approach, but i want to know why its failing. http://www.codechef.com/viewsolution/1909473 answered 18 Mar '13, 16:19

Any border test cases? I am still getting WA http://www.codechef.com/viewsolution/1954203 answered 20 Mar '13, 19:17

@anton_lunyov >> Please clarify this:
In the loop part, the begin() and end() functions are called each time an iteration occurs, so isn't it time consuming? Instead if we just store
and
before entering the loop and then use x and y, do we save some time? answered 22 Mar '13, 22:49
I think all that the .begin() function does is accessing elements on well known positions that are known ahead of time and thus takes constant time, and that gives you no advantage, but maybe doing such modification on the .end() part might help, Im not sure if the gains would be significant though
(23 Mar '13, 00:46)

Can anybody explain what is the runtime of Union/Find approach. I used union by size approach. answered 04 Apr '13, 17:27

Plz help me out in this..i thought a lot on this problem and finally did it..though i got a WA i can't figure out what was wrong with my code...i wrote a c program which can be seen at answered 04 Apr '13, 18:21

please suggest me in whatcase my code giving wrong answer.....http://www.codechef.com/viewsolution/1976048 answered 04 Apr '13, 20:03
y *= size[i]; Here the value of y can cross the limit of int and hence wrong answer. Make y long long int and you should be fine.
(04 Apr '13, 20:30)

url: http://www.codechef.com/viewsolution/1930307 I m getting WA cna someone help in finding a test case where my code fails?? thank u in advance....:) answered 12 Apr '13, 23:23

can any one tell me whats wrong with this code.. its running on my pc but giving compilation error http://ww2.codechef.com/viewsolution/2076377 answered 01 May '13, 18:48

well sorry for reviving such an old topic but there seems to be an error with my implementation,i dont know why i am getting a TLE here is my submission http://www.codechef.com/viewsolution/2779075 i have used a dfs and a linked list approach could anyone illuminate my mistake. answered 07 Oct '13, 21:18

What is wrong with thi?? https://www.codechef.com/viewsolution/14792552 answered 05 Aug, 01:09

Whats wrong with this https://www.codechef.com/viewsolution/14984690 answered 16 Aug, 00:56

Answer is hidden as author is suspended. Click here to view.
answered 16 Aug, 03:54

Can someone please point out the mistake in this code? Code(https://www.codechef.com/viewsolution/15077459) Thanks :) answered 22 Aug, 21:53

I used weighted quick union for this, which can be improved further using path compression. My solution : http://www.codechef.com/viewplaintext/1869801
http://www.codechef.com/viewsolution/1939836 getting wrong ans..really pissed off :( please find the error...thanx in advance...
I m getting SIGSEGV but i dont know why i am getting this... intializing like this mark=vector<int>(n,0) i am getting correct answer.. but when i try to do vector<int> mart(n,0) i am getting SIGSEGV.. what is wrong with this...plz answer me.. http://www.codechef.com/viewsolution/4372844