MST Edge Check

题目描述

给定一个无向带权图，判断每条边是否可以被包含在某个最小生成树中。

输入格式

第一行包含两个整数 n 和 m：节点数和边数。节点编号为 1,2,$\dots$,n。 接下来的 m 行描述每条边。每行有三个整数 a, b, w：表示在节点 a 与 b 之间有一条权重为 w 的边。 你可以假设图是连通且无重边的，并且每条边在图中最多出现一次。

输出格式

对于输入顺序中的每条边，如果它可以被包含在某个最小生成树中则输出 YES，否则输出 NO。

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

NO
YES
YES
YES
YES
YES

提示

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

标签: CSES3407|高级图论问题

来源

CSES3407|高级图论问题