In problem 160D — Round #111 (Div 2), I write my solution base on this submission: https://codeforces.com/contest/160/submission/95615534 (ignore the TLE part please).
This is my final solution afterward : https://codeforces.com/contest/160/submission/131991008
My question is, why the DFS function ran fine when passing the index of the edge (idx
) as parent (par
) parameter :
void dfs(int u, int par)
{
timer++; num[u] = low[u] = timer;
for (auto e : ne[u])
{
int v = e.first, idx = e.second;
if (idx == par) {continue;} // this line
if (num[v] == 0)
{
dfs(v, idx); //and this line
low[u] = min(low[u], low[v]);
if (low[v] == num[v]) //is bridge
{
res[idx] = 1;
}
}
else
{
low[u] = min(low[u], num[v]);
}
}
}
but return wrong answer when using the node (v
)itself :
void dfs(int u, int par)
{
timer++; num[u] = low[u] = timer;
for (auto e : ne[u])
{
int v = e.first, idx = e.second;
if (v == par) {continue;} //this line
if (num[v] == 0)
{
dfs(v, u); // and this line
low[u] = min(low[u], low[v]);
if (low[v] == num[v]) //is bridge
{
res[idx] = 1;
}
}
else
{
low[u] = min(low[u], num[v]);
}
}
}
I'm asking this cause in bridges' finding function normally I write, passing v
as parent works just fine. Am I missing something here?
P.S: The test that return different answer for the 2 cases is just the first sample test:
4 5
1 2 101
1 3 100
2 3 2
2 4 2
3 4 1