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了，可以的话，请您参考添加页面，与大家一起分享你的题解！