ICPC澳门 K - Link-Cut Tree（图论 + dfs + 并查集）

题目传送门：K-Link-Cut Tree_第46屆ICPC 東亞洲區域賽（澳門）(正式賽） (nowcoder.com)

题目大意

有T个测试样例。

给定n个点，m条边，第i条边的权值为2的i次方，求图中权值之和最小的环的边的编号（从小到大）。

思路

看到2的i次方，不难想到用贪心，从小到大（也就是按照输入顺序）遍历所有边，一旦出现环，就直接输出这个环的边的编号就行了，一定是权值和最小的。

这里可以用并查集判断是否有环，方法是如果新的边{x, y}已经相连那么连接之后就会形成第一个环，然后忽略后面的输入，再用dfs配合栈来将环输出。

注意：这题十分毒瘤，我的root函数用while循环来写就TLE了（进行了路径压缩），但是用递归方式写就不会T，真的无语了。

代码

#include <bits/stdc++.h>
#define pb push_back
#define int long long
#define fi first
#define se second
using namespace std;

inline int readInt()
{
     int s = 0,w = 1;char ch = getchar();
     while(ch < '0' || ch > '9'){if(ch == '-')w = -1;ch = getchar();}
     while('0' <= ch && ch <= '9')s = s * 10 + ch - '0',ch = getchar();
     return s * w;
}

typedef pair<int, int> PII;
const int maxn = 1e5 + 10;
int pre[maxn];

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

int root(int x)
{
     if(pre[x] == x)return x;
     return pre[x] = root(pre[x]);
}

int stk[maxn], top = 0;
bitset<maxn> vis;

void dfs(int ed, int x, int fa) 
{
    vis[x] = true;
    if(ed == x) 
    {
        sort(stk + 1, stk + top + 1);
        for (int i = 1; i <= top; ++i)
            printf("%d%c", stk[i], i == top ? '\n' : ' ');
    }
    for(auto i : g[x])
     {
        int y = i.fi, id = i.se;
        if (y == fa || vis[y])continue;
        stk[++top] = id;
        dfs(ed, y, x);
        --top;
    }
}

void solve()
{
     int n = readInt(), m = readInt();
     for(int i = 1;i <= n; ++ i)
     {
          pre[i] = i;
          g[i].clear();
          vis[i] = 0;
     }
     int st = 0;//起始点 
     bool tag = 0;//已经有环 
     for(int i = 1;i <= m; ++ i)
     {
          int x = readInt(), y = readInt();
          if(tag)continue;
          g[x].pb({y, i});
          g[y].pb({x, i});
          if(root(x) == root(y))
          {
               st = x;
               tag = 1;
          }
          pre[root(x)] = root(y);
     }
     if(tag)
     {
          top = 0;
          for(auto i : g[st])
          {
               stk[++ top] = i.se;
               dfs(st, i.fi, st);
               -- top;
          }
     }
     else printf("-1\n");
}

signed main()
{
     int T = readInt();
     while(T --)solve();
     return 0;
}