Tien_Noob1235's blog

By Tien_Noob1235, history, 2 years ago, In English

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

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it