aboutsummaryrefslogtreecommitdiff
path: root/find_critical_edge_tree.cpp
blob: 31c033890a1aad80edf73c2d09e3d03ee1e85a99 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
// 1489. Find Critical and Pseudo-Critical Edges in Minimum Spanning Tree
#include "leetcode.h"

/*
 * given a weighted undirected connected graph with 'n' vertices numbered from 0
 * to 'n - 1' and an array 'edges' where 'edges[i] = [ai, bi, weighti]'
 * represents a bidrectional and weighted edge between nodes 'ai' and 'bi'. a
 * minimum spanning tree (MST) is a subset of the graph's edges that connects
 * all vertices withoutcycles and with the minimum possible total edge weight.
 * find all critical and pseudo-critical edges in the given graph's MST. an MST
 * edge whose deletion from the graph would casue the MST weight to increase is
 * called a critical edge. on the other hand, a pseudo-critical edge is that
 * which can appear in some MSTs butnot all. note that you can return the
 * indices of the edges in any order.
 */

class UnionFind {
  vector<int> f, rank;

public:
  UnionFind(int n) {
    rank = vector<int>(n, 1);
    f.resize(n);
    for (int i = 0; i < n; ++i)
      f[i] = i;
  }
  int find(int x) {
    if (f[x] == x)
      return x;
    else
      return f[x] = find(f[x]);
  }
  void uinion(int x, int y) {
    int fx = find(x), fy = find(y);
    if (fx == fy)
      return;
    if (rank[fx] > rank[fy])
      swap(fx, fy);
    f[fx] = fy;
    if (rank[fx] == rank[fy])
      rank[fy]++;
  }
};

class Solution {
  int get_mst(const int n, const vvd(int) & edges, int block_edge,
              int pre_edge = -1) {
    UnionFind uf(n);
    int weight = 0;
    if (pre_edge != -1) {
      weight += edges[pre_edge][2];
      uf.uinion(edges[pre_edge][0], edges[pre_edge][1]);
    }
    for (int i = 0; i < edges.size(); ++i) {
      if (block_edge == i)
        continue;
      const auto &e = edges[i];
      if (uf.find(e[0]) == uf.find(e[1]))
        continue;
      uf.uinion(e[0], e[1]);
      weight += e[2];
    }
    for (int i = 0; i < n; ++i)
      if (uf.find(i) != uf.find(0))
        return 1e9 + 7;
    return weight;
  }

public:
  vvd(int) findCriticalAndPseudoCriticalEdges(int n, vvd(int) & edges) {
    for (int i = 0; i < edges.size(); ++i)
      edges[i].push_back(i);
    sort(
        edges.begin(), edges.end(),
        [](const vector<int> &a, const vector<int> &b) { return a[2] < b[2]; });
    int origin_mst = get_mst(n, edges, -1);
    vector<int> critical, non_critical;
    for (int i = 0; i < edges.size(); ++i) {
      if (origin_mst < get_mst(n, edges, i))
        critical.push_back(edges[i][3]);
      else if (origin_mst == get_mst(n, edges, -1, i))
        non_critical.push_back(edges[i][3]);
    }
    return {critical, non_critical};
  }
};

int main() {
  Solution obj;
  vvd(int) e1 = {{0, 1, 1}, {1, 2, 1}, {2, 3, 2}, {0, 3, 2},
                 {0, 4, 3}, {3, 4, 3}, {1, 4, 6}},
           e2 = {{0, 1, 1}, {1, 2, 1}, {2, 3, 1}, {0, 3, 1}};
  for (auto i : obj.findCriticalAndPseudoCriticalEdges(5, e1))
    for (auto j : i)
      printf("%d ", j);
  printf("\n");
  for (auto i : obj.findCriticalAndPseudoCriticalEdges(4, e2))
    for (auto j : i)
      printf("%d ", j);
  printf("\n");
}