Mr. Kitayuta's Colorful Graph

2024-01-13 19:58
文章标签 mr kitayuta colorful graph

本文主要是介绍Mr. Kitayuta's Colorful Graph,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

数据量很小用搜索或并查集应该都能过

题目要求:

从一个点到另一个点可以经过多少条不同的边

思路:

为每一条不同编号的边建一个并查集,查看有多少条边可以使这两个点有共同的父节点

                                        B. Mr. Kitayuta's Colorful Graph

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 vidirectly or indirectly.

Input

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 — aibi (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.

Output

For each query, print the answer in a separate line.

Examples

input
4 5
1 2 1
1 2 2
2 3 1
2 3 3
2 4 3
3
1 2
3 4
1 4
output
2
1
0
input
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
output
1
1
1
1
2

Note
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.

#include<stdio.h>
#include<string.h>
#define maxn 105
int pre[maxn][maxn];
void Union(int x,int y,int z);
int find(int a,int b);
int main() 
{int n,m,q;memset(pre,0,sizeof(pre));scanf("%d%d",&n,&m);for(int i=1;i<=m;i++){for(int j=1;j<=n;j++){pre[i][j]=j;}}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,ans=0;scanf("%d%d",&a,&b);for(int j=1;j<=m;j++){int fa,fb;fa=find(a,j);fb=find(b,j);if(fa==fb)ans++;}printf("%d\n",ans);}return 0;
}
void Union(int x,int y,int z)
{int fx,fy;fx=find(x,z);fy=find(y,z);if(fx!=fy)pre[z][fx]=fy;
}
int find(int a,int b)
{int r=a;while(r!=pre[b][r])r=pre[b][r];while(a!=pre[b][a]){int s=a;a=pre[b][a];pre[b][s]=r;}return r;
}



这篇关于Mr. Kitayuta's Colorful Graph的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/602616

相关文章

图神经网络框架DGL实现Graph Attention Network (GAT)笔记

参考列表: [1]深入理解图注意力机制 [2]DGL官方学习教程一 ——基础操作&消息传递 [3]Cora数据集介绍+python读取 一、DGL实现GAT分类机器学习论文 程序摘自[1],该程序实现了利用图神经网络框架——DGL,实现图注意网络(GAT)。应用demo为对机器学习论文数据集——Cora,对论文所属类别进行分类。(下图摘自[3]) 1. 程序 Ubuntu:18.04

SIGMOD-24概览Part7: Industry Session (Graph Data Management)

👇BG3: A Cost Effective and I/O Efficient Graph Database in ByteDance 🏛机构:字节 ➡️领域: Information systems → Data management systemsStorage management 📚摘要:介绍了字节新提出的ByteGraph 3.0(BG3)模型,用来处理大规模图结构数据 背景

A Comprehensive Survey on Graph Neural Networks笔记

一、摘要-Abstract 1、传统的深度学习模型主要处理欧几里得数据(如图像、文本),而图神经网络的出现和发展是为了有效处理和学习非欧几里得域(即图结构数据)的信息。 2、将GNN划分为四类:recurrent GNNs(RecGNN), convolutional GNNs,(GCN), graph autoencoders(GAE), and spatial–temporal GNNs(S

Neighborhood Homophily-based Graph Convolutional Network

#paper/ccfB 推荐指数: #paper/⭐ #pp/图结构学习 流程 重定义同配性指标: N H i k = ∣ N ( i , k , c m a x ) ∣ ∣ N ( i , k ) ∣ with c m a x = arg ⁡ max ⁡ c ∈ [ 1 , C ] ∣ N ( i , k , c ) ∣ NH_i^k=\frac{|\mathcal{N}(i,k,c_{

boost.graph之属性

相关宏 BOOST_INSTALL_PROPERTY #define BOOST_INSTALL_PROPERTY(KIND, NAME) \template <> struct property_kind<KIND##_##NAME##_t> { \typedef KIND##_property_tag type; \} 最终形式为 template <> struct proper

【ZOJ】3874 Permutation Graph 【FFT+CDQ分治】

传送门:【ZOJ】3874 Permutation Graph 题目分析: 容易知道一个个连通块内部的标号都是连续的,否则一定会有另一个连通块向这个连通块建边,或者这个连通块向另一个连通块建边。而且从左到右左边的连通块内最大的标号小于右边连通块内最小的标号。 然后我们可以构造dp方程: dp[n]=n!−i!∗dp[n−i] \qquad \qquad dp[n] = n! - i! *

【HDU】5333 Undirected Graph【LCT+BIT】

传送门:【HDU】5333 Undirected Graph my  code: my~~code: #pragma comment(linker, "/STACK:1024000000")#include <stdio.h>#include <string.h>#include <map>#include <algorithm>using namespace std ;typed

【HDU】5574 Colorful Tree【子树染色,询问子树颜色数——线段树+bit+lca+set】

题目链接:【HDU】5574 Colorful Tree 题目大意:对一个子树染色,询问一个子树的颜色数。 题目分析: set set维护每种颜色所在的 dfs dfs序区间,修改均摊 nlogn nlogn。 #include <bits/stdc++.h>using namespace std ;typedef long long LL ;typedef pair < int , i

CodeForces 404C Restore Graph

题意: n个点的图  最大度为k  已知从某个点到每个点的距离dis[i]  求  这幅图的边 思路: 告诉了距离  很容易想到dis是从距离为0的那个点开始bfs求出来的 那么复原这幅图的办法就是重新构造这棵bfs形成的树就好了 每层利用点数计算一下是不是违反了最大度k的限制 这里注意  只有dis=0的那个点可以连出k条边  其余的只有k-1条(因为它们还和父亲连着一条边)

知识图谱(knowledge graph)——概述

知识图谱总结 概念技术链概括通用知识图谱和垂直领域知识图谱国内外开放知识图谱 技术链详解知识获取知识融合知识表示知识推理知识存储 知识图谱构建流程其他挑战跨语言知识抽取跨语言知识链接 思考参考 概念 知识图谱(Knowledge Graph)以结构化的形式描述客观世界中概念、实体及其关系。是融合了认知计算、知识表示与推理、信息检索与抽取、自然语言处理、Web技术、机器学习与大数据