原题解链接:https://ac.nowcoder.com/discuss/150246
转化后的题意为:给出一张图,有多少条边一定在最小生成树上
考虑这样的做法:
按照Kruskal算法的思想,对边按照权值排序,然后依次加入,同时用并查集维护两点之间的连通性
本题最难处理的也就是权值相同的边,我们可以放在一起考虑
如果一条边连接的两个点已经联通了,那么不需要考虑这条边
否则,把该边加入到新图中, tarjan一遍求出所有的桥即可,可以证明这些边一定在最小生成树上
时间复杂度:
/*
void make_data(int test) {
int N = 4e4, M = 1e5, bg = rand() % N + 1, Lim = 1e9, cnt = 0;
static int a[101];
for(int i = 1; i <= 100; i++) a[++cnt] = i * i;
random_shuffle(a + 1, a + cnt + 1);
printf("%d %d %d\n", N, M, bg);
for(int i = 2; i <= N; i++) printf("%d %d %d\n", i, rand() % (i - 1) + 1, a[rand() % cnt + 1]);
for(int i = N + 1; i <= M + 1; i++) {
int k = rand() % N + 1;
int y = (k + rand()) % N + 1;
if(y == k) y = (y + 1) % N + 1;
printf("%d %d %d\n", k, y, a[rand() % cnt + 1]);
}
}
*/
#include<bits/stdc++.h>
#define Pair pair<int, int>
#define MP(x, y) make_pair(x, y)
#define fi first
#define se second
using namespace std;
const int MAXN = 1e6 + 10;
inline int read() {
char c = getchar(); int x = 0, f = 1;
while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
return x * f;
}
int N, M, Begin;
vector<Pair> v[MAXN];
struct Edge {
int u, v, w, id;
bool operator < (const Edge &rhs) const {
return w < rhs.w;
}
}E[MAXN];
int dfn[MAXN], low[MAXN], tot, fa[MAXN], ans[MAXN];
void tarjan(int x, int fa) {
dfn[x] = low[x] = ++tot;
for(int i = 0, to, id; i < v[x].size(); i++) {
if((id = v[x][i].se) == fa) continue;
to = v[x][i].fi;
if(!dfn[to]) {
tarjan(to, id), low[x] = min(low[x], low[to]);
if(low[to] > dfn[x]) ans[id] = 1;
}
else low[x] = min(low[x], dfn[to]);
}
}
int find(int x) {
return x == fa[x] ? fa[x] : fa[x] = find(fa[x]);
}
map<pair<int, int>, bool> mp;
int main() {
// freopen("a1.in", "r", stdin);
N = read(), M = read(); Begin = read();
for(int i = 1; i <= N; i++) fa[i]= i;
for(int i = 1; i <= M; i++) {
int x = read(), y = read(), z = read();
E[i] = (Edge) {x, y, z, i};
if(mp[MP(x, y)] || mp[MP(y, x)] || (x == y)) {puts("GGG"); return 0; }
mp[MP(x, y)] = mp[MP(y, x)] = 1;
}
sort(E + 1, E + M + 1);
int nxt;
for(int i = 1; i <= M; i = nxt + 1) {
nxt = i + 1;
for(; E[i].w == E[nxt].w; nxt++); nxt--;
for(int j = i; j <= nxt; j++) {
int x = find(E[j].u), y = find(E[j].v);
if(x == y) continue;
v[x].push_back(MP(y, j));
v[y].push_back(MP(x, j));
}
for(int j = i; j <= nxt; j++) {
int x = find(E[j].u), y = find(E[j].v);
if(x == y || dfn[x]) continue;
tarjan(x, -1);
}
for(int j = i; j <= nxt; j++) {
int x = find(E[j].u), y = find(E[j].v);
if(x == y) continue;
v[x].clear(); v[y].clear();
dfn[x] = 0; dfn[y] = 0;
fa[x] = y;
}
}
int tot = 0;
for(int i = 1; i <= M; i++) tot += ans[i];
cout << tot;
return 0;
}
/*
3 3 1
1 2 1
1 3 1
2 3 2
*/