B. Mr. Kitayuta’s Colorful Graph
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output
Mr. Kitayuta has just bought an undirected graph consisting ofnvertices andmedges. The vertices of the graph are numbered from 1 ton. Each edge, namely edgei, has a colorci, connecting vertexaiandbi.
Mr. Kitayuta wants you to process the followingqqueries.
In thei-th query, he gives you two integers —uiandvi.
Find the number of the colors that satisfy the following condition: the edges of that color connect vertexuiand vertexvidirectly or indirectly.
Input
The first line of the input contains space-separated two integers —nandm(2≤n≤100,1≤m≤100), denoting the number of the vertices and the number of the edges, respectively.
The nextmlines contain space-separated three integers —ai,bi(1≤ai<bi≤n) andci(1≤ci≤m). Note that there can be multiple edges between two vertices. However, there are no multiple edges of the same color between two vertices, that is, ifi≠j,(ai,bi,ci)≠(aj,bj,cj).
The next line contains a integer —q(1≤q≤100), denoting the number of the queries.
Then followsqlines, containing space-separated two integers —uiandvi(1≤ui,vi≤n). It is guaranteed thatui≠vi.
Output
For each query, print the answer in a separate line.
Sample test(s)
input
4 51 2 11 2 22 3 12 3 32 4 331 23 41 4
output
210
input
5 71 5 12 5 13 5 14 5 11 2 22 3 23 4 251 55 12 51 51 4
output
11112
Note
Let’s consider the first sample.
The figure above shows the first sample.Vertex1and vertex2are connected by color1and2.Vertex3and vertex4are connected by color3.Vertex1and vertex4are not connected by any single color.
题意：现有n个点m条边的无向图，每条边都有一种颜色，然后有q次询问，x y询问点x到点y共有几种颜色的边将他们连起来（不同颜色的边不能混在一起，要分开看）
思路：二维并查集，每种颜色维护一个并查集，，查询时看某一种颜色下两个点是否有共同的father。
代码：
#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <cmath>#include <string>#include <map>#include <stack>#include <vector>#include <set>#include <queue>#pragma comment (linker,"/STACK:102400000,102400000")#define maxn 1005#define MAXN 2005#define mod 1000000009#define INF 0x3f3f3f3f#define pi acos(-1.0)#define eps 1e-6#define lson rt<<1,l,mid#define rson rt<<1|1,mid+1,rtypedef long long ll;using namespace std;int n,m;int color[110];int father[110][110];void init(){for (int i=0;i<=110;i++)for (int j=0;j<=110;j++)father[i][j]=j;}int find_father(int c,int x)//递归写法{if (x!=father[c][x])father[c][x]=find_father(c,father[c][x]);return father[c][x];}//int find_father(int c,int x) //非递归写法//{// int r=x,i,j;// while(r!=father[c][r])//r=father[c][r];// i=x;// while(i!=r)// {//j=father[c][i];//father[c][i]=r;//i=j;// }// return r;//}int main(){while (~scanf("%d%d",&n,&m)){init();int a,b,c;memset(color,0,sizeof(color)); //记录下用了哪些颜色for (int i=0;i<m;i++){scanf("%d%d%d",&a,&b,&c);color[c]=1;//printf("+++\n");int fa=find_father(c,a);int fb=find_father(c,b);if (fa!=fb)father[c][fa]=fb;}int q,x,y;scanf("%d",&q);while (q–){scanf("%d%d",&x,&y);int ans=0;for (int i=1;i<=m;i++){if (color[i]){if (find_father(i,x)==find_father(i,y))ans++;}}printf("%d\n",ans);}}return 0;}
何不去远方！昆明呀——赶一个花海;
