C++ 双向道路路口 习题

Question

问题描述：
一位教授喜欢沿着马路走，尤其是在有环的小路上道路和十字路口，他的想法是将每条道路的用糟糕程度来表述。
他居住的城市的道路系统是一组双向道路，每条道路连接两个路口。 人们可以从任何其他路口到达每个路口，并且没有任何道路直接将任何路口与其本身相连。碰巧的是，这个城市的每条道路的糟糕程度都不同。
如果存在一条环路（一条没有重复道路的路径，起点和终点在同一个路口）教授决定称其为“糟糕的”，其中这条道路是他指定的最高糟糕级别。
现在他希望知道他所在的城市里是否有任何不糟糕的道路。

输入：

1. 一行包括 n and m (n, m ≤ 10^5) 分别代表路口和道路的数量
2. m 行描述道路的线，其中第 i 条线包含 ui 和 vi ——由第 i 条道路连接的路口的索引。道路按照糟糕程度的升序排列，并以相同的顺序从 1 到 m 编号。保证每个路口都可达从其他路口到达，并且没有道路将一个路口连接到它自己，但是两个路口之间可能有几条道路。

输出：
在第一行输出不糟糕的道路的数量（int值）。在下一行按升序输出这些道路的编号。

其实题目本身就没有很理解到底要用什么方法，希望可以给出答案最好加一些解释！谢谢啦

Answer 1

#include <bits/stdc++.h>

using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, m;
    cin >> n >> m;
    vector<int> s(n);
    for(int i=0;i<n;i++) s[i] = i;
    vector<int> ans;
    function<int(int)> FIND = [&](int x){
        return x == s[x] ? x : s[x] = FIND(s[x]);
    };
    for(int i=1;i<=m;i++){
        int u, v;
        cin >> u >> v;
        u -= 1;
        v -= 1;
        u = FIND(u);
        v = FIND(v);
        if(u != v){
            s[u] = v;
            ans.push_back(i);
        }
    }
    cout << ans.size() << '\n';
    for(auto i : ans) cout << i << ' ';
    return 0;
}