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

- Website name is hackerrank not hackerearth.
- 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.

You tagged tourist for that

What should be the solution for that question ?

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.

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);
```

}

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.

Please learn to read what is written above asking same question again.