web analytics

JZOJ 4822 完美标号 解题报告

Description

给定M个二元组(A_i, B_i),求X_1, ..., X_N满足:对于任意(A_i, B_i),有|X_{A_i} - X_{B_i}| = 1成立。
 

Input

第1行,2个整数N、M。
第2行到第M + 1行,2个整数A_i和B_i。

Output

第1行,1个字符串,"YES"表示有解,"NO"表示无解。
第2行,N个整数,X_1, X_2, ..., X_N,无解则不输出。
要求|X_i| <= 1,000,000,000,任意一解均可。
 

Sample Input

Sample Output

 

Data Constraint

对于40%的数据,1 <= N <= 10。
对于100%的数据,1 <= N <= 10,000,0 <= M <= 100,000,1 <= A_i, B_i <= N。

分析:

这道题正解是并查集来做.其实这道题就用图的遍历就可以解决.先走一遍DFS填好所有的点.之后再枚举每一条边.如果两个节点相同的值.那么这个不是正确的,如果所有的点都解决了.那么这就结束了.

这道题其实可以拿BFS过

其实BFS也可以过.可能时间会长一点.这个方法在寻找的时候就加上判断.可能会快一点吧.不过应该还好.这个方式感觉如果没解其实是没有搜完整个图的.不过感觉没什么太大区别

Post a Comment

You must be logged in to post a comment.