Codeforces Round #286 (Div. 2) B 并查集
1 second
256 megabytes
standard input
standard output
Mr. Kitayuta has just bought an undirected graph consisting of n vertices and m edges. The vertices of the graph are numbered from 1 to n. Each edge, namely edge i, has a color ci, connecting vertex ai and bi.
Mr. Kitayuta wants you to process the following q queries.
In the i-th query, he gives you two integers — ui and vi.
Find the number of the colors that satisfy the following condition: the edges of that color connect vertex ui and vertex vi directly or indirectly.
The first line of the input contains space-separated two integers — n and m (2 ≤ n ≤ 100, 1 ≤ m ≤ 100), denoting the number of the vertices and the number of the edges, respectively.
The next m lines contain space-separated three integers — ai, bi (1 ≤ ai < bi ≤ n) and ci (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, if i ≠ j, (ai, bi, ci) ≠ (aj, bj, cj).
The next line contains a integer — q (1 ≤ q ≤ 100), denoting the number of the queries.
Then follows q lines, containing space-separated two integers — ui and vi (1 ≤ ui, vi ≤ n). It is guaranteed that ui ≠ vi.
For each query, print the answer in a separate line.
4 5
1 2 1
1 2 2
2 3 1
2 3 3
2 4 3
3
1 2
3 4
1 4
2
1
0
5 7
1 5 1
2 5 1
3 5 1
4 5 1
1 2 2
2 3 2
3 4 2
5
1 5
5 1
2 5
1 5
1 4
1
1
1
1
2
Let's consider the first sample.
The figure above shows the first sample.
- Vertex 1 and vertex 2 are connected by color 1 and 2.
- Vertex 3 and vertex 4 are connected by color 3.
- Vertex 1 and vertex 4 are not connected by any single color.
题意:n个点的图 m条边 两个点间可以有多条边 但是两点间相同颜色的边只能有一条 q个查询 判断 u-v间可以通过多少种颜色的边联通
题解:并查集处理
#pragma comment(linker, "/STACK:102400000,102400000")
#include <cstdio>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <cctype>
#include <map>
#include <set>
#include <queue>
#include <bitset>
#include <string>
#include <complex>
#define ll __int64
#define mod 1000000007
using namespace std;
int n,m;
int fa[][];
int find(int root,int c)
{
if(fa[c][root]==root)
return root;
else
return fa[c][root]=find(fa[c][root],c);
}
void unio(int a,int b,int c)
{
int aa=find(a,c);
int bb=find(b,c);
if(aa!=bb)
fa[c][aa]=bb;
}
int main()
{
scanf("%d %d",&n,&m);
for(int i=;i<=m;i++)
for(int j=;j<=n;j++)
fa[i][j]=j;
int a,b,c;
for(int i=;i<=m;i++)
{
scanf("%d %d %d",&a,&b,&c);
unio(a,b,c);
}
int q;
scanf("%d",&q);
for(int i=;i<=q;i++)
{
scanf("%d %d",&a,&b);
int ans=;
for(int j=;j<=m;j++)
{
if(find(a,j)==find(b,j))
ans++;
}
printf("%d\n",ans);
}
return ;
}
最新文章
- 关于welcome-file-list(欢迎页)不起作用的解决办法
- html不使用cache数据
- Daily English
- achartengine 绘图表神器
- UTF8转码, 考虑利用app转好再传, CC2541转太麻烦了...
- C#多态问题
- Win10无法上网提示缺少一个或者多个网络协议的处理方法
- Spring基础知识汇总 Java开发必看
- [AS3]as3与JS的交互(AS3调用JS)实例说明
- Lambda高手之路第二部分
- Uber广州车主官网本周将暂关闭
- hive------ Group by、join、distinct等实现原理
- 前端开发中的JS调试技巧
- Spring Security测试代码
- 如何优化JavaScript的构造函数
- Asp.Net_from标签中的Enctype=multipart/form-data作用
- MathType调整矩阵分隔线粗细的方法
- ajax 与 form 提交的区别
- Java数据结构和算法(一):简介
- java.lang.UnsupportedClassVersionError: action/Login : Unsupported major.minor version 52.0 (unable to load class action.Login)异常