Skip to content

11310: 【原1310】MST

题目

题目描述

author: 陈昕昀 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1310

Description

给定一个n个点m条边的带权无向图,相信大家都知道这幅图的最小生成树怎么求。现要求编写一个程序解决如下问题:对于每一条边,判断这条边在最小生成树中出现的情况,在每棵最小生成树中均不出现则输出0,均出现则输出1,其他情况输出2。

Input Format

第一行包含两个整数n和m。

接下来m行,每行三个整数x,y,w表示x与y之间有一条权值为w的边。

Output Format

输出m行,每行一个整数,第i行的输出表示第i条边在最小生成树中出现的情况,如果第i条边在所有最小生成树中均不出现则输出0,均出现则输出1,其他情况输出2。

Sample Input 1

3 3
1 2 1
2 3 1
1 3 1

Sample Output 2

2
2
2

Sample Input 1

3 3
1 2 1
2 3 1
1 3 2

Sample Output 2

1
1
0

Hint

对于30%的数据,n≤1000,n-1≤m≤2000

对于100%的数据,2≤n≤10^5,n-1≤m≤2*10^5,1≤边权≤10^6,保证图连通。

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!