【并查集缩点+tarjan无向图求桥】Where are you @牛客练习赛32 D

PROBLEM

时空裂隙

SOLUTION

楠神口胡算法我来实现系列

从小到大枚举边权，对于当前的权值，在当前的图找出所有等于该权值的边，把这些边的顶点用其在并查集中的代表元（即fa[x]）替换，然后建图，求所建图的桥边。求完之后把每条边的两个顶点合并（缩点），然后枚举下一个权值。最后统计桥边数量和就是答案。

CODE

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int MAXN = 2e5 + 5;

struct edge {

    int v, w, nex;

} ed[MAXN * 2];

int head[MAXN], tot;

void addedge(int u, int v,int w) {

    tot++;

    ed[tot].v = v;

    ed[tot].w = w;

    ed[tot].nex = head[u];

    head[u] = tot;

}

set<int> ss;

struct data{

    int ind,w;

}eg[MAXN*2];

bool cmp(data a,data b){

    return a.w<b.w;

}

int n,m;

bool bridge[MAXN*2];

int dfn[MAXN],low[MAXN],num;

vector<pair<int,int>> g[MAXN];

set<int> nd;

int fa[MAXN];

int DjsGet(int x){

    if(x==fa[x])return x;

    return fa[x] = DjsGet(fa[x]);

}

void tarjan(int x,int in_edge){

    dfn[x] = low[x] = ++num;

    for(auto ver:g[x]){

        int y = ver.first;

        int i = ver.second;

        if(!dfn[y]){

            tarjan(y,i);

            low[x] = min(low[x],low[y]);

            if(low[y]>dfn[x]){

                bridge[i] = bridge[i^1] = true;

            }

        }

        else if(i!=(in_edge^1))

            low[x] = min(low[x],dfn[y]);

    }

}

int main() {

    scanf("%d%d%*d",&n,&m);

    tot = 1;

    for(int i=1;i<=m;i++){

        int u,v,w;

        scanf("%d%d%d",&u,&v,&w);

        addedge(u,v,w);

        addedge(v,u,w);

        ss.insert(w);

        eg[i]= {i*2,w};

    }

    sort(eg+1,eg+m+1,cmp);//边按权值从小到大排序

    for(int i = 1;i<=n;i++)fa[i] = i;

    int pos = 1;

    for(auto curval:ss){

        int pre = pos;

        //建子图

        for(pos;eg[pos].w<=curval&&pos<=m;pos++){

            int ind = eg[pos].ind;

            int x = ed[ind^1].v,y = ed[ind].v;

            int fx = DjsGet(x);

            int fy = DjsGet(y);

            if(fx==fy)continue;

            g[fx].push_back(make_pair(fy,ind));

            g[fy].push_back(make_pair(fx,ind^1));

            nd.insert(fx);

            nd.insert(fy);

        }

        //求桥

        for(auto i:nd){

            if(!dfn[i])tarjan(i,0);

        }

        //init

        for(auto i:nd){

            dfn[i] = low[i] = 0;

            g[i].clear();

        }

        num = 0;

        nd.clear();

        //缩点

        for(int i= pre;i<pos;i++){

            int ind = eg[i].ind;

            int x = ed[ind^1].v,y = ed[ind].v;

            int fx = DjsGet(x);

            int fy = DjsGet(y);

            if(fx==fy)continue;

            fa[fx] = fy;

        }

    }

    int ans = 0;

    for(int i = 2;i<=tot;i+=2){

        if(bridge[i])ans++;

    }

    printf("%d\n",ans);

    return 0;

}