Hangzhou Electric Power Multi-School 6 1010. Planar graph

1010
最小生成树

题意

给出一个 $n$ 个点 $m$ Side plan,Ask at least how many edges can be removed to make every part of the plane reachable,Output the solution with the minimum number of edges to be deleted and the lexicographical order of the edge numbers.

思路

You can build a dual graph and run itmst,但有更简单的方法.
Drawing and finding satisfaction“Every part of the floor plan is mutually reachable”The picture must be a tree or a forest,（In fact, there must be no loop,Acyclic is a tree）,That is, the remaining graph after we delete the edge must be a tree/森林,So run according to the side number from big to trotKruscal就可以了,对第 $i$ 号边,If the two connected points are in the same set,Then this edge must be deleted.This satisfies the lexicographical order of the deleted edges as small as possible.

代码

void solve() {
    
    cin >> n >> m;
    for(int i = 1; i <= n; i++) {
    
    	fa[i] = i;
    }
    for(int i = 1; i <= m; i++) {
    
    	cin >> e[i].u >> e[i].v;
    }
    vector<int> ans;
    for(int i = m; i; i--) {
    
    	if(find(e[i].u) == find(e[i].v)) {
    
    		ans.pb(i);
    	}
    	else {
    
    		merge(e[i].u, e[i].v);
    	}
    }
    sort(ans.begin(), ans.end());
    cout << ans.size() << endl;
    for(auto i : ans) {
    
    	cout << i << ' ';
    }
    cout << endl;
}