暑假集训——个人训练赛04——B题

并查集

题意：有n个点和m条路，每条路都有一个颜色，相同的颜色的路才能贯通，问输入的两点间有几条路可走。

思路：输入时记录每个点的最终祖先，然后询问时判断是否有公共的最终祖先，有的话就可以走。注意这里要多一维来表示路的颜色。

#include<stdio.h>

const int MAX=101;
int pre[MAX][MAX];

int Find(int x,int c)//递归查找最终祖先
{
	if(pre[x][c]==x) return x;
	return pre[x][c]=Find(pre[x][c],c);
}

void Union(int u,int v,int c)//并
{
	int a=Find(u,c);
	int b=Find(v,c);
	if(a==b) return;
	else
	{
		pre[a][c]=pre[b][c];
	}
}

int main()
{
	int n,m,q;
	while(~scanf("%d%d",&n,&m))
	{
		for(int i=1;i<=n;i++)//注意初始化
		{
			for(int j=1;j<=m;j++)
			{
				pre[i][j]=i;
			}
		}
		for(int i=0;i<m;i++)
		{
			int a,b,c;
			scanf("%d%d%d",&a,&b,&c);
			Union(a,b,c);
		}
		scanf("%d",&q);
		for(int i=0;i<q;i++)
		{
			int a,b;
			scanf("%d%d",&a,&b);
			int num=0;
			for(int j=1;j<=m;j++)
			{
				int c=Find(a,j);
				int d=Find(b,j);
				if(c==d) num++;//判断是否有公共的最终祖先
			}
			printf("%d\n",num);
		}
	}
	return 0;
}