FIRESC - Editorial

Any border test cases? I am still getting WA
http://www.codechef.com/viewsolution/1954203

@anton_lunyov >> Please clarify this:

for (VI::iterator v = a[u].begin(); v != a[u].end(); ++v) {
	// *v is the adjacent vertex itself
	if (!mark[*v]) {
		// if it was not visited before we move to it
		dfs(*v);
	}
}

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

x = a[u].begin() 

and

y = a[u].end() 

before entering the loop and then use x and y, do we save some time?

Can anybody explain what is the runtime of Union/Find approach. I used union by size approach.

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
http://www.codechef.com/viewsolution/1900728

please suggest me in whatcase my code giving wrong answer…http://www.codechef.com/viewsolution/1976048

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…:slight_smile:

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

Please help . Getting Wrong answers for even test case!!!
link to my code -> http://ideone.com/lU40Sl

2 Likes

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.

What is wrong with thi??
https://www.codechef.com/viewsolution/14792552

Whats wrong with this https://www.codechef.com/viewsolution/14984690

Please star my projects and contribute if you are interested.

  1. https://github.com/ArmenGabrielyan16/DiceRoller
  2. https://github.com/ArmenGabrielyan16/SuperLibrary

Can someone please point out the mistake in this code?

Code-(https://www.codechef.com/viewsolution/15077459)

Thanks :slight_smile:

such a nice problem, thank you codechef.

1 Like

Used union find but kept getting TLE. Code:https://ideone.com/gDZvZc
Would be really helpful if someone could point out the mistake in this.

very good question …

You have loop for(int j=i; j<n; j++) after each call to dfs. In the case of no edges in the graph you will have O(N^2) solution. Obviously it should get TLE :slight_smile:

@anton_lunyov >> So, if I consider the case of graph consisting of no edges separately, will it run within TL?

Replace c[p[i]]++ by c[find(i)]++
p[i] is not always the actual root of the disjoint set containing i.
Namely, after link operation.

1 Like

http://www.codechef.com/viewplaintext/1916644