[WC2021] 括号路径

Link

Description

一个 (n) 个点 (m) 条边的图，一条边 ((u,v,w)) 实际由一条从 (u) 到 (v) 类型为 (w) 的左括号的边和一条 (v) 到 (u) 的类型为 (w) 的右括号的边。询问有多少个无序点对 ((u,v))，存在一条 (u) 到 (v) 或 (v) 到 (u) 的合法括号路径。

Solution

考场上总没脑子，感觉还是太慌了，没有静下来思考。其实一开始发现常规方法不可做时就应该想有什么好的性质的，以后应该注意。

不容易发现如果 (u) 到 (v) 存在合法括号路径，那么将该路径反过来，实际上括号也取反了（这是由于题目的有向边的很好的性质），那么 (v) 到 (u) 也有合法路径。那么 ((u,v)) 等价于 ((v,u))，那么就可以转换为连通性问题。

又可以发现，如果有 ((x,y)) 又有 ((y,z))，那么就有 ((x,z))。因为两个合法括号序列拼起来也合法。有点并查集的感觉了。这就提示我们可以维护若干个点集，点集里的点都是相互可达的。

如何才能知道两个点集可不可以合并？我们知道，一个合法的括号序列需要添加至少两个括号才能形成一个新的合法括号序列，也就是说要走至少两条边。那么这两条边就会有一个中间节点，所以我们可以考虑通过这个中间节点（或是点集）来更新。又发现， (A) 和 (B) 可以合并，当且仅当存在一个 (C)，有 ((A,C,w)) 和 ((B,C,w))，所以我们可以考虑维护每个点集的入边的边集，每次新加入一种类型的入边，就将该入边所指的点集和现有的该类型的入边所指的点集合并。合并点集的同时，入边边集也要合并，然后再产生新的合并操作。

连通性可以用并查集，边集的维护可以用启发式合并，用 hash 存边，那么复杂度 (O(n log n))

#include<stdio.h>
#include<unordered_map>
#include<queue>
#include<vector>
using namespace std;
#define It unordered_map<int,int>::iterator

struct E{int u,v;};
const int N=3e5+7;
unordered_map<int,int> mp[N];
queue<E> Q;

inline int read(){
    int x=0,flag=1; char c=getchar();
    while(c<'0'||c>'9'){if(c=='-') flag=0;c=getchar();}
    while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+c-48;c=getchar();}
    return flag? x:-x;
}

int n,m,K,fa[N],sz[N];

inline void swap(int &x,int &y){x^=y,y^=x,x^=y;}

inline int find(int x){
    if(fa[x]==x) return x;
    return fa[x]=find(fa[x]);
}

int main(){
    n=read(),m=read(),K=read();
    for(int i=1;i<=n;i++) fa[i]=i;
    for(int i=1,u,v,w;i<=m;i++){
        v=read(),u=read(),w=read();
        if(mp[u][w]) Q.push((E){mp[u][w],v});
        else mp[u][w]=v;
    }
    while(!Q.empty()){
        E t=Q.front(); Q.pop();
        int fa_u=find(t.u),fa_v=find(t.v);
        if(fa_u==fa_v) continue;
        if(mp[fa_u].size()<mp[fa_v].size())
            swap(fa_u,fa_v);
        for(It i=mp[fa_v].begin();i!=mp[fa_v].end();i++)
            if(mp[fa_u][i->first]) Q.push((E){mp[fa_u][i->first],i->second});
            else mp[fa_u][i->first]=i->second;
        fa[fa_v]=fa_u,mp[fa_v].clear();
    }
    for(int i=1;i<=n;i++) sz[find(i)]++;
    long long ans=0;
    for(int i=1;i<=n;i++) ans+=1ll*sz[i]*(sz[i]-1)>>1;
    printf("%lld",ans);
}