MST Edge Set Check

题目描述

给定一个无向带权图和若干条边的集合，对于每个集合判断这些边是否可以被包含在某个最小生成树中。

输入格式

第一行包含三个整数 n、m 和 q：节点数、边数和边集合数。节点编号为 1,2,\dots,n。 接下来的 m 行描述边。每行包含三个整数 a、b、w：表示在节点 a 和 b 之间有一条权重为 w 的边。输入顺序中边的编号为 1,2,\dots,m。 接下来的 2q 行描述这些边集合。对于每个集合，第一行包含其大小，第二行包含它的边的编号。所有集合中边的总数至多为 m。 你可以假设图是连通且简单的，并且每条边在图中至多出现一次。

输出格式

对于每个边集合，如果这些边可以被包含在某个最小生成树中则输出 YES，否则输出 NO。

5 6 4
1 2 4
1 3 2
2 4 2
3 4 1
3 5 3
4 5 3
3
2 3 4
1
1
2
2 6
2
5 6

YES
NO
YES
NO

提示

$1 \le n \le 10^5$ $1 \le m, q \le 2 \cdot 10^5$ $1 \le a,b \le n$ $1 \le w \le 10^9$

标签: CSES3408|高级图论问题

来源

CSES3408|高级图论问题