原题链接： Edges in MST
参考题解： Edges in MST

题目描述

给出一个 $n$ 个点 $m$ 条边的无向连通图，求问每条边在最小生成树中的出现情况。
如果不在任何最小生成树中出现，输出none
如果在至少一棵最小生成树中出现，输出at least one
如果再所有最小生成树中都出现，输出any
$n, m \leq 1e5$

输入样例

4 5
1 2 101
1 3 100
2 3 2
2 4 2
3 4 1

输出样例

none
any
at least one
at least one
any

$tarjan$ 求桥

首先对所有边从小到大排序，然后同时处理边权相同的边

• 如果边连接的两个点已经在同一连通块中，那么这条边必然不在任何最小生成树中

• 剩下的边要么一定在最小生成树中，要么可能再最小生成树中，把这条边建出来

如果某条边一定在最小生成树中，断开这条边会导致连通块数量增加（截止到目前考虑到的这些边形成的图中）

而这与桥的定义相同，所以我们对于当前考虑的这些边涉及到的点，跑一下tarjan给桥打上标记即可

最后再遍历一下这些边，把他们连接的点合并，并清空这些边

时间复杂度 $O(mlogm)$

C++ 代码

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>

using namespace std;

const int N = 100010, M = N << 1;

struct Edge{
    int a, b, w, type, id;
    bool operator< (const Edge &W) const {
        return w < W.w;
    }
}edges[N];

int h[N], e[M], num[M], ne[M], idx;
void add(int a, int b, int c)
{
    e[idx] = b, num[idx] = c, ne[idx] = h[a], h[a] = idx ++;
}

int p[N];
int find(int x)
{
    if(p[x] != x)  p[x] = find(p[x]);
    return p[x];
}

int dfn[N], low[N], tot;

void tarjan(int u, int fa)          //  fa为抵达u节点的边的编号
{
    dfn[u] = low[u] = ++ tot;
    for(int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i], k = num[i];
        if(k == fa)  continue;
        if(!dfn[j])
        {
            tarjan(j, k);
            low[u] = min(low[u], low[j]);
            if(low[j] > dfn[u])  edges[k].type = 2;
        }
        else
            low[u] = min(low[u], dfn[j]);
    }
}

int res[N];

int main()
{
    memset(h, -1, sizeof h);

    int n, m;
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i++)  p[i] = i;

    for(int i = 0; i < m; i ++)
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        edges[i] = (Edge){a, b, c, 0, i};
    }
    sort(edges, edges + m);

    for(int i = 0, j; i < m; i = j + 1)
    {
        j = i;
        while(j + 1 < m and edges[j + 1].w == edges[i].w)  j ++;

        for(int k = i; k <= j; k ++)
        {
            int a = find(edges[k].a), b = find(edges[k].b);
            if(a != b)
            {
                add(a, b, k);
                add(b, a, k);
                edges[k].type = 1;
            }
        }
        for(int k = i; k <= j; k ++)
        {
            int a = find(edges[k].a), b = find(edges[k].b);
            if(a != b and !dfn[a])  tarjan(a, -1);
        }
        for(int k = i; k <= j; k ++)
        {
            int a = find(edges[k].a), b = find(edges[k].b);
            if(a != b)
            {
                h[a] = h[b] = -1;
                dfn[a] = dfn[b] = 0;
                p[a] = b;
            }
        }
    }

    for(int i = 0; i < m; i ++)  res[edges[i].id] = edges[i].type;

    for(int i = 0; i < m; i ++)
    {
        if(!res[i])  puts("none");
        else if(res[i] == 1)  puts("at least one");
        else  puts("any");
    }
    return 0;
}