题解：P8056 C 图上的数

· · 题解

思路

定义连接的两点中有恰好一个被删除的边为半孤边，出边中有至少一条半孤边的点为半孤点。有一个显然的性质：删掉半孤点一定会导致新的孤边产生。

首先，第一条边一定要最先成为孤边，所以要先删掉它连接的两个点。

然后，接下来删除的边一定是可以被最先删除的最小的边。那么，这条边应满足：要么它是一条半孤边，要么它连接的点不全是半孤点。

为什么呢？如果一条边连接的两点都是半孤点，那么无论先删去哪个，都会导致一些新的、并非这条边的孤边产生。

考虑进行如下过程：先将所有边丢进堆里，每次取出一条最小的，如果它满足条件，就删掉它连接的点，否则直接跳过。在删点时（设该点为 u），检查与这个点相邻的所有点 v，若 v 没有被删除，就让它变成半孤点，并把连接 u,v 的边 w 重新丢进堆中；若 v 已被删除，那么连接 u,v 的边肯定也变成孤边了，也记录下来。

注意一件事情。如果删除的两点中有半孤点（设该点为 u），那么要先检查删掉它后，会新增的孤边。记这些半孤边中最大的为 w_m，找到 u 相邻的所有结点 v，若 v 满足：v 不是半孤点，v 与 u 的连边 w 比 w_m 小，那么将点 v 也先删掉。至于为什么，比较显然，可以自己画一画。

这样做的复杂度是 O((m+n)\log m)。复杂度请感性理解。

代码

#include <bits/stdc++.h>
#define ll long long

using namespace std;

const int maxn = 1e6 + 5;

vector<pair<int, int> > G[maxn];
int us[maxn], vs[maxn], half[maxn], del[maxn], ans[maxn];
priority_queue<int, vector<int>, greater<int> > q;

int main(){
    int n, m;
    scanf("%d %d", &n, &m);
    for(int i = 1; i <= m; i ++){
        scanf("%d %d", &us[i], &vs[i]);
        G[us[i]].push_back(make_pair(vs[i], i)), G[vs[i]].push_back(make_pair(us[i], i));
        q.push(i);
    }
    int k = 0;
    while(!q.empty()){
        int x = q.top();
        q.pop();
        if(del[us[x]] && del[vs[x]]) continue;
        if(del[us[x]] || del[vs[x]]){
            if(del[vs[x]]) swap(us[x], vs[x]);
            half[vs[x]] = 0, del[vs[x]] = 1;
            ans[++ k] = x;
            int max1 = 0;
            for(int i = 0; i < G[vs[x]].size(); i ++){
                int j = G[vs[x]][i].first, w = G[vs[x]][i].second;
                if(del[j] && j != us[x]) max1 = max(max1, w);
            }
            for(int i = 0; i < G[vs[x]].size(); i ++){
                int j = G[vs[x]][i].first, w = G[vs[x]][i].second;
                if(!del[j]){
                    if(!half[j] && w < max1){
                        del[j] = 1;
                        for(int l = 0; l < G[j].size(); l ++){
                            int t = G[j][l].first;
                            if(!del[t]) half[t] = 1;
                        }
                    }else half[j] = 1, q.push(w);
                }
                if(del[j] && j != us[x]) ans[++ k] = w;
            }
            continue;
        }
        if(half[us[x]] && half[vs[x]]) continue;
        if(half[us[x]] || half[vs[x]]){
            del[us[x]] = del[vs[x]] = 1;
            if(half[us[x]]) swap(us[x], vs[x]);
            half[vs[x]] = 0;
            for(int i = 0; i < G[us[x]].size(); i ++){
                int j = G[us[x]][i].first;
                if(!del[j]) half[j] = 1;
            }
            ans[++ k] = x;
            int max1 = 0;
            for(int i = 0; i < G[vs[x]].size(); i ++){
                int j = G[vs[x]][i].first, w = G[vs[x]][i].second;
                if(del[j] && j != us[x]) max1 = max(max1, w);
            }
            for(int i = 0; i < G[vs[x]].size(); i ++){
                int j = G[vs[x]][i].first, w = G[vs[x]][i].second;
                if(!del[j]){
                    if(!half[j] && w < max1){
                        del[j] = 1;
                        for(int l = 0; l < G[j].size(); l ++){
                            int t = G[j][l].first;
                            if(!del[t]) half[t] = 1;
                        }
                    }else half[j] = 1, q.push(w);
                }
                if(del[j] && j != us[x]) ans[++ k] = w;
            }
        }else{
            del[us[x]] = del[vs[x]] = 1;
            ans[++ k] = x;
            for(int i = 0; i < G[us[x]].size(); i ++){
                int j = G[us[x]][i].first;
                if(!del[j]) half[j] = 1;
            }
            for(int i = 0; i < G[vs[x]].size(); i ++){
                int j = G[vs[x]][i].first;
                if(!del[j]) half[j] = 1;
            }
        }
    }
    ll res = 0;
    for(int i = 1; i <= m; i ++){
        res ^= 1ll * ans[i] * i;
    }
    printf("%lld\n", res);
    return 0;
}