|
|
| Line 1: |
Line 1: |
| − | <pre>
| + | |
| − | 1. DFS from any vertex when found back edge add it to F.
| |
| − | 2. Applying the Kruskal's algorithm
| |
| − | - First multiply the weights of all edges by -1
| |
| − | - If an edge is found during the algorithm execution, both ends of which belong to the same component, add it to F
| |
| − | By multiplying all edges by -1, the edges with the highest weight will be processed first => the edges with the lowest weight will be added to F
| |
| − | An alternative statement of the problem from point 2 is to find the complement to the maximum spanning tree.
| |
| − | </pre>
| |
| − | --[[User:Bkarpov96|Bkarpov96]] ([[User talk:Bkarpov96|talk]]) 15:38, 22 July 2020 (UTC)
| |
