USACO 2018 January Contest, Gold Cow at Large

Problems and Contests
#1

I was reading the uasaco guide solution for the cow at large problem and I had a problem within the line 41 to 45

for (int i = 0; i < N; i++) {
	if (inDeg[i] == 1) {
		bfs(i);
	}
}

that this block won’t run in O(n^2) and get TLE?

#2

That runs in O(N)?

#3

I’m not really sure that’s why I’m asking :sweat_smile:

#4

but I think it must run in O(N*N).

#5

yes, worst case is \mathcal O(N^2)

#6
#7

Oh, sorry, I didn’t look at the code inside the if statement. My bad.