FIRESC - Editorial

Any border test cases? I am still getting WA

@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

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() 


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

please suggest me in whatcase my code giving wrong answer…


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

Please help . Getting Wrong answers for even test case!!!
link to my code ->


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 i have used a dfs and a linked list approach could anyone illuminate my mistake.

What is wrong with thi??

Whats wrong with this

Please star my projects and contribute if you are interested.


Can someone please point out the mistake in this code?


Thanks :slight_smile:

such a nice problem, thank you codechef.

1 Like

Used union find but kept getting TLE. Code:
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