A and B wants to reach some destination in an undirected graph using the least number of unique edges. Find the count of unique edges.
Let's say the two paths come out to be this.. A-x-y-D B-y-D
Output : 4
Explanation : A-x, x-y, y-D and B-y
Follow up: What if there are multiple sources?
Can someone help me to solve this optimally?
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3792 |
| 2 | VivaciousAubergine | 3647 |
| 3 | Kevin114514 | 3603 |
| 4 | jiangly | 3583 |
| 5 | turmax | 3559 |
| 6 | tourist | 3541 |
| 7 | strapple | 3515 |
| 8 | ksun48 | 3461 |
| 9 | dXqwq | 3436 |
| 10 | Otomachi_Una | 3413 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 157 |
| 2 | adamant | 153 |
| 3 | Um_nik | 147 |
| 4 | Proof_by_QED | 146 |
| 5 | Dominater069 | 145 |
| 6 | errorgorn | 142 |
| 7 | cry | 139 |
| 8 | YuukiS | 135 |
| 9 | TheScrasse | 134 |
| 10 | chromate00 | 133 |
Do a BFS from nodes A, B and D, now you know the distance from A, B and D to every node. There are two cases:
1) the paths A — D and B — D don't intersect
2) the paths meet at some node X(A — X — D and B — X — D)
the first case is just $$$d_{DA} + d_{DB}$$$
in the second case to find the node X we can just try for every node $$$d_{AX} + d_{BX} + d_{DX}$$$
Got it. But what about the case where we have multiple sources?
How many sources are we talking about? Also what are the other constraints?
There can be more nodes other than A and B
Assume:
Nodes: A, B, C, D, E, F, G, H
A, B, C, D are the source.
E is the destination.
I mean how many sources and/or nodes can there be? 10? 100? $$$10^5$$$?
What's the source of the problem?
No Source as such, got it from leetcode discussion.
Please share it to make sure you're not cheating