[Nowcoder272D] Where are you (最小生成树，缩点，割边)

发表于 | 分类于 ， | 评论数： | 阅读次数：

题目链接：https://ac.nowcoder.com/acm/contest/272/D

求无向图中必然在最小生成树上出现的边的条数。

根据最小生成树的构造方法可以知道，当最小生成树不唯一时，可以用某一条边替换树上相同权值的边。
考虑kruskal算法，我们按照相同的边进行分组，每次处理一个组，并把这组边加到之前已经处理好的连通块上后跑tarjan求桥。在这个组里如果有某条边是桥，那么这条边一定是会选中的就可以计数，之后清理一下标记就可以了。

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
102
103
104
105
106
107
108
109
110
111
#include <bits/stdc++.h>
using namespace std;

typedef struct Edge {
  int u, v;
  int w;
}Edge;
const int maxn = 202001;
int n, m, p;
int pre[maxn];
vector<Edge> e;

int find(int x) {
  return x == pre[x] ? x : pre[x] = find(pre[x]);
}

void unite(int x, int y) {
  pre[find(x)] = find(y);
}

typedef struct Tarjan {
  struct Edge {
    int u, v, next;
    int idx;
  };
  Edge edge[maxn];
  int ecnt, d, Y;
  int head[maxn], bridge[maxn];
  int low[maxn], dfn[maxn];

  Tarjan() {
    memset(head, -1, sizeof head);
    memset(bridge, 0, sizeof bridge);
    memset(low, 0, sizeof low);
    memset(dfn, 0, sizeof dfn);
    ecnt = 0; d = 0; Y = 0;
  }

  void adde(int u, int v) {
    edge[ecnt].u = u, edge[ecnt].v = v;
    edge[ecnt].idx = Y;
    edge[ecnt].next = head[u]; head[u] = ecnt++;
    edge[ecnt].u = v, edge[ecnt].v = u;
    edge[ecnt].idx = Y++;
    edge[ecnt].next = head[v]; head[v] = ecnt++;
  }

  void dfs(int u, int p) {
    low[u] = dfn[u] = ++d;
    for(int i = head[u]; ~i; i=edge[i].next) {
      int v = edge[i].v;
      int idx = edge[i].idx;
      if(p == idx) continue;
      if(!dfn[v]) {
        dfs(v, idx);
        low[u] = min(low[u], low[v]);
        if(low[v] == dfn[v]) {
          bridge[i] = 1;
        }
      }
      else low[u] = min(low[u], dfn[v]);
    }
  }
}Tarjan;

signed main() {
  // freopen("in", "r", stdin);
  int u, v, w;
  while(~scanf("%d%d%d",&n,&m,&p)) {
    Tarjan t;
    e.clear();
    for(int i = 1; i <= n; i++) {
      pre[i] = i;
    }
    for(int i = 0; i < m; i++) {
      scanf("%d%d%d",&u,&v,&w);
      e.emplace_back(Edge({u,v,w}));
    }
    sort(e.begin(), e.end(), [](Edge a, Edge b) { return a.w < b.w; });
    for(int i = 0; i < m; ) {
      int k = i;
      while(k < m && e[k].w == e[i].w) k++;
      for(int j = i; j < k; j++) {
        u = find(e[j].u), v = find(e[j].v);
        if(u == v) continue;
        t.adde(u, v);
      }
      for(int j = i; j < k; j++) {
        u = find(e[j].u), v = find(e[j].v);
        if(u == v) continue;
        if(!t.dfn[u]) t.dfs(u, -1);
        if(!t.dfn[v]) t.dfs(v, -1);
      }
      for(int j = i; j < k; j++) {
        u = find(e[j].u), v = find(e[j].v);
        if(u == v) continue;
        t.dfn[u] = t.dfn[v] = 0;
        t.low[u] = t.low[v] = 0;
        t.head[u] = t.head[v] = -1;
        unite(u, v);
      }
      i = k;
    }
    int ret = 0;
    for(int i = 0; i < t.ecnt; i++) {
      if(t.bridge[i]) ret++;
    }
    printf("%d\n", ret);
  }
  return 0;
}