 # 0-1 Graph hackerrank

Question 0-1 Graph
The editorial says to do bfs , assign all 1 weights n travel from back and if a value is greater than next, assign min. value from right.
Is there a proof why this works>?
@tourist

2 Likes
1. Website name is hackerrank not hackerearth.
2. Why does it work?
It doesnt work.
It fails on testcase
``````5 4
2 5
4 3
1 4
2 4
``````

Most of the AC soln will print 6 but correct answer is 5.

6 Likes

You tagged tourist for that     5 Likes

What should be the solution for that question ?

@aryanc403 do u mean editorial is wrong? If so, pls send correct Sol(your approach) and intituition

I dont know the correct soln. Soln I wrote for an AC is same as editorial. But it is a wrong soln.

I just gave a counter testcase for the soln written in editorial.

4 Likes

My solution gets WA in three of fourteen tests.

My logic is:
Each graph can be transformed to a tree which will have the same solution. This tree is constructed such that each vertex > parent of this vertex.
Initially, the tree is linear ie 1 <- 2 <- 3 <- … <- n. Then, go through the edges of the graph. For each edge (a, b) where a < b, set tree[b] = min(tree[b], a). Then, we traverse the array in reverse manner reducing values so as to make it a non-decreasing array. But the values are not distances, they are parent vertices. The last loop calculates the sum of distances.

``` void solve() { ll n, nf_edges; scan(n);scan(nf_edges); vector<ll> tree(n + 1); for (ll i = 1; i <= n; ++i) { tree[i] = i - 1; } //print_container(tree); ll one, two, large, small; while (nf_edges --) { scan(one); scan(two); large = max(one, two); small = min(one, two); tree[large] = min(tree[large], small); } //print_container(tree); for (ll i = n, level = n; i > 1; i--) { if (level > tree[i]) { level = tree[i]; } else { tree[i] = level; } } //print_container(tree); ll summ = 0; for (ll i = 2, mul = 0; i <= n; ++i) { if (tree[i - 1] != tree[i]) { mul++; } summ += mul; } pnl(summ); } ```

what should be the solution this question??
@aryanc403
@vijju123

I submitted a solution considering this type of test case. What i simply do is when i am doing bfs i just see if the node im going to has a the number lesser than the node im coming from , if yes then it will have distance of the node im coming from (and not + 1) .And after i have traversed the whole graph and made my dist array. I just make sure that it is non decreasing.