并查集不仅可以用于一维，也可以用于高维。
此题的大意是10W个点10W条边（有多种颜色），10W个询问：任意两个节点之间可以由几条相同颜色的路径连通。
这里要用到高维的并查集，定义fa[u][c]=v表示节点u的颜色c属于集合v，由于无法开出这么大的二维数组，且实际边的数量很少，可以考虑使用map。
每次加边的时候，如果该节点u的颜色c不属于任何集合，则将u作为当前集合的根。每次加入一条边，相当于合并两个不同的集合。
询问的时候可以暴力查找，同时记录哪些被查找过，下次不再重复查找。枚举u的每一种颜色集合，验证v的这个颜色是否与u属于同一集合，即u，v能否由同一颜色的路径连通。
这题有个坑点，就是普通的map会超时，要使用unordered_map。
#include<bits/stdc++.h>
#define rep(i,n) for(i=1;i<=n;i++)
using namespace std;
const int maxn=;
unordered_map<int,int>fa[maxn],ou[maxn];
int n,m;
int getfa(int v,int c)
{
if(fa[v][c]==v)return v;
return fa[v][c]=getfa(fa[v][c],c);
}
void work(int x,int y,int c)
{
if(fa[x].find(c)==fa[x].end())fa[x][c]=x; //root
if(fa[y].find(c)==fa[y].end())fa[y][c]=y;
int f1=getfa(x,c);
int f2=getfa(y,c);
if(f1!=f2)
fa[f1][c]=f2;
}
int main()
{
scanf("%d%d",&n,&m);
int i;
rep(i,m)
{
int x,y,c;
scanf("%d%d%d",&x,&y,&c);
work(x,y,c);
}
int q;
scanf("%d",&q);
rep(i,q)
{
int x,y;
int ans=;
scanf("%d%d",&x,&y);
if(ou[x].find(y)!=ou[x].end())
{
printf("%d\n",ou[x][y]);
continue;
}
int s1=fa[x].size(); //total color
int s2=fa[y].size();
if(s1>s2)swap(x,y);
for(auto u: fa[x])
if(fa[y].find(u.first)!=fa[y].end())
if(getfa(x,u.first)==getfa(y,u.first)) //be in the same set
++ans;
ou[x][y]=ou[y][x]=ans;
printf("%d\n",ans);
}
return ;
}