**i am getting frustrated with this problem, but not able to find what is going wrong with my approach**

**PLEASE SOME ONE HELP**

problem link:- Telecom Towers

mysolution link in java:-- solution1

mySolution Link for those who dont want to unlock solution solution2

**my solution is partially accepted, 8 out 51 test cases were accepted**

## MyApproach:-##

**after seeing** editorial i came to know that this problem will be solved using maximum bipartite matching

- created a graph which have only those nodes in edges which have distance equal to d
- applied bipartite algo, to find max flow, max flow or(total maximum augementing path count will be our answer)

Your soln fails at -

```
4 1
0 1
0 2
1 0
2 0
```

Answer should be 2. You have assumed that graph is a connected component.

Similar Question - http://codeforces.com/contest/687/problem/A (Do try this.)

My failed approach - http://codeforces.com/contest/687/submission/38090506 (Exact same approach as yours).

##
Click to view

You will need a loop for temp from 0 to n-1 (If 0 based indexing).

I cannot modify your soln to get AC because I understand java less. Due to its similarity with c++ . I found the mistake but cannot add more to it.

Pseudo code -

##
Click to view

int ans=0;

for(temp=0;temp<n;++temp)

if(visited[temp]==true)

continue;

your current codeâ€¦ Bfs/Dfs with current implementation

find no of 1 and 2 which are marked now.

add minimum of both to answer.

My AC approach-

##
Click to view

http://codeforces.com/contest/687/submission/38090585 .

2 Likes

Your submission is locked

Have to solve that before looking at ur solnâ€¦

Bro, One more solution link updatedâ€¦ if u donâ€™t want to unlock

thankx Brother , u saved me, â€śdil se dua nikal rhi h tumhare liyeâ€ť, bhagwan tumhe jaldi jaldi 7 star bna deâ€¦

passed all test cases except 1 due to poor bipartite matching algoâ€¦

but

â€śfind no of 1 and 2 which are marked now. add minimum of both to answer.â€ť will not work otherwise for every bipartite problem solution will be min of â€śnumber of element in both groupâ€ť

for example:- there are 3 nodes in group 1(marked color 1) named as 1,2,3 and 3 nodes in group2(marked color=2) named as a,b,câ€¦

now connections are as followed:-

1->a,b,c

2->a

3->a

ur answer is min(3,3)=3 but actual is 2

1 Like