【Codeforces 1166F】Vicky's Delivery Service | Mrsrz's blog

并查集，set 启发式合并。

题目大意：

给定一张 $n$ 个点 $m$ 条边的无向图，边有颜色，需要支持以下操作：

• 给定 $u,v,c$，在 $u$ 和 $v$ 之间连一条颜色为 $c$ 的无向边。
• 给定 $u,v$，要求找一条从 $u$ 出发到 $v$（顺序不能调换）的路径，使得第 $2i$ 条边和第 $2i-1$ 条边的颜色相同（如果经过的边数是奇数则最后一条边没有限制）。问是否存在。

题解：

考虑点 $u,v,w$，如果 $u,v$ 和 $u,w$ 之间存在颜色相同的边，则 $v$ 和 $w$ 就可以互相到达。

我们用并查集来维护可以互相到达的点的连通性。然后查询边数为偶数的路径的情况时，只需要判断两个点是否在同一个连通块内即可。

当然，如果要两两都连边的话，一个菊花复杂度就炸了。由于我们只需要维护连通性，所以一个点只需要和另外的一个点连边就行了。

我们用 map 维护和 $u$ 有颜色为 $c$ 边相连的随便一个结点就行了。

这样只处理了边数为偶数的情况，对于边数为奇数，即最后再随便走一条边的情况还没有处理。

我们考虑对每个并查集上的连通块，维护它走一条边能到的结点集合。用 set 存储，在加边的时候加入 set 里即可。

然后并查集上合并两个连通块的时候，我们也需要把 set 合并起来。直接启发式合并即可。

时间复杂度 $O((n+m)\log ^2 n)$。

Code：

#include<cstdio>
#include<set>
#include<map>
using namespace std;
const int N=1e5+5;
set<int>st[N];
map<int,int>mp[N];
int n,m,q,fa[N];
inline int find(int x){while(x!=fa[x])x=fa[x]=fa[fa[x]];return x;}
inline void merge(int x,int y){
    int u=find(x),v=find(y);
    if(u==v)return;
    if(st[u].size()<st[v].size())u^=v^=u^=v;
    fa[v]=u;
    for(int i:st[v])st[u].insert(i);st[v].clear();
}
inline void addedge(int u,int v,int c){
    st[find(u)].insert(v);
    if(mp[u].count(c)){
        int x=mp[u][c];
        merge(v,x);
    }else mp[u][c]=v;
}
int main(){
    scanf("%d%d%*d%d",&n,&m,&q);
    for(int i=1;i<=n;++i)fa[i]=i;
    while(m--){
        int u,v,c;
        scanf("%d%d%d",&u,&v,&c);
        addedge(u,v,c),addedge(v,u,c);
    }
    while(q--){
        char op[3];int u,v,c;
        scanf("%s%d%d",op,&u,&v);
        if(*op=='+'){
            scanf("%d",&c);
            addedge(u,v,c),addedge(v,u,c);
        }else{
            int x=find(u),y=find(v);
            if(x==y||st[x].count(v))puts("Yes");else puts("No");
        }
    }
    return 0;
}