题意:n个点,m条边,问有哪条边是去掉之后,会造成之前连通的点不再连通的?n <= 150, m <= 5000.
思路:连通算法有dfs+bool数组记录,或者dsu,感觉dsu更方便。m * n 不超过1e6,直接暴力。
class DisjointSet{
public:DisjointSet(int sz): sz_(sz){set_size_.assign(sz_, 1);fa_.resize(sz_);iota(fa_.begin(), fa_.end(), 0);}int findSet(int x){ return fa_[x] == x ? x : fa_[x] = findSet(fa_[x]); }int getSetSize(int x){ return set_size_[findSet(x)]; }bool unionSet(int x, int y){x = findSet(x);y = findSet(y);if (x == y){return false;}fa_[x] = y;set_size_[y] += set_size_[x];return true;}private:int sz_;vector<int> fa_;vector<int> set_size_;};void solve(){int n, m;cin >> n >> m;DisjointSet dsu(n + 1);vector<vector<int>> al(n + 1);vector<pair<int, int>> edges;for (int i = 1; i <= m; ++i){int u, v;cin >> u >> v;dsu.unionSet(u, v);if (u > v){swap(u, v);}edges.emplace_back(u, v);}vector<int> pos;for (int i = 0; i < m; ++i){DisjointSet dsu2(n + 1);for (int j = 0; j < m; ++j){if (j != i){dsu2.unionSet(edges[j].first, edges[j].second);}}for (int k = 1; k <= n; ++k){if (dsu2.getSetSize(k) != dsu.getSetSize(k)){pos.emplace_back(i);break;}}}sort(pos.begin(), pos.end(), [&](int i, int j){return edges[i].first != edges[j].first ? edges[i].first < edges[j].first : edges[i].second < edges[j].second;});for (const int& index : pos){cout << edges[index].first << " " << edges[index].second << "\n";}}
总结:使用下标数组排序,可以避免再次存储答案占用更多内存。 unionSet里面返回值一定要写。