【ICPC 2022 澳门站】K题 Link-Cut Tree 题解

题目大意

给定一个包含 $n$ 个点、$m$ 条边的图，第 $i$ 条边的长度是 $2^i$。

求一条长度最短的环的长度和边的编号，如果没有输出 $-1$。

题目链接

思路

可以发现，前 $i-1$ 条边的长度加起来也比第 $i$ 条边短。所以我们尽量用前面的边来构成环。

那么如何判断是否存在环呢？我们从第一条一条地往图中加边，同时用并查集记录已经连在一起的点，一旦我们加入一条边时，发现连接的两个点已经在一个并查集中了，那就说明把这条边加进去时，就存在了一条环。我们用拓扑排序找到它即可。

代码

#include <cstdio>
#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;

const int maxN = 2e5 + 7;

int T, n, m, head[maxN], cnt, fa[maxN], st, vis[maxN], cnt2, d[maxN], ans[maxN];

struct Edge {
    int from, to, dis;
}e[maxN << 1], e2[maxN << 1];

struct Now {
    int val, point;
}now[maxN];

inline void add(int u, int v, int w)
{
    e[++cnt].from  = u; e[cnt].to = v;
    e[cnt].dis = w;
}

inline void add2(int u, int v, int w)
{
    e2[++cnt2].from = head[u]; e2[cnt2].to = v;
    e2[cnt2].dis = w; head[u] = cnt2;
}


bool cmp(Edge x, Edge y)
{
    return x.dis < y.dis;
}

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

void bfs()
{
    queue<int> q;
    for(int i = 1; i <= n; ++i)
        if(d[i] == 1)
            q.push(i);
    while(!q.empty()) {
        int x = q.front(); q.pop();
        for(int i = head[x]; i; i = e2[i].from) {
            int y = e2[i].to;
            d[y]--;
            ans[e2[i].dis] = 1;
            if(d[y] == 1)
                q.push(y);
        }
    }
}

int main()
{
    scanf("%d", &T);
    while(T--) {
        memset(head, 0, sizeof head); memset(vis, 0, sizeof vis); memset(ans, 0, sizeof ans); memset(d, 0, sizeof d);
        cnt = cnt2 = 0;
        scanf("%d%d", &n, &m);
        for(int i = 1; i <= m; ++i) {
            int x, y; scanf("%d%d", &x, &y);
            add(x, y, i);
        }
        for(int i = 1; i <= n; ++i)
            fa[i] = i;
        sort(e + 1, e + 1 + m, cmp);
        bool succ = false;
        for(int i = 1; i <= m; ++i) {
            int x = e[i].from, y = e[i].to;
            int fx = find(x), fy = find(y);
            if(fx == fy) {
                st = i;
                for(int j = 1; j <= i; ++j) {
                    add2(e[j].from, e[j].to, e[j].dis);
                    add2(e[j].to, e[j].from, e[j].dis);
                    d[e[j].from]++; d[e[j].to]++;
                }
                bfs();
                succ = true;
                break;
            }
            fa[fx] = fy;
        }
        if(succ) {
            int i = 1;
            for(; i <= st; ++i)
                if(ans[i] == 0) {
                    printf("%d", i++);
                    break;
                }
            for(;i <= st; ++i)
                if(ans[i] == 0)
                    printf(" %d", i);
            printf("\n");
        }
        else
            printf("-1\n");
    }
    return 0;
}