• auto-gen TOC: {:toc}

组队排位赛12 SpbKOSHP 19

没找到英文题解（只有俄文题解？）

Gym 102396C 暴力 复杂度分析

解法：并查集维护连通性，vector<int> frient存朋友关系，当两个连通块合并时，遍历节点数较少的连通块的节点v，遍历u:frient[v]，判断答案是否+1即可

时间复杂度$O(k+(q+m)log_2q)$？？

struct union_set{
    const static int max_node = 1e5 + 1000;
    int head[max_node];
    
    int find(int x){return head[x]==x?x:head[x]=find(head[x]);}
    void init(int node_cnt){for(int i=node_cnt; i>=0; i--) head[i] = i;}
    bool merge(int u, int v){
        u = find(u), v = find(v);
        if(u == v) return false;
        if(un[u].size() > un[v].size()) swap(u, v);
        for(int nd:un[u]){
            for(int f:frient[nd]){
                if(v == find(f)) ans[nd]++, ans[f]++;
            }
        }
        for(int nd:un[u]) un[v].push_back(nd);
        un[u].clear();
        head[u] = v;
        return true;
    }
}unset;

Gym 102396K LCT*

Gym 102396J 数学*