Problem

Description

给定M个二元组 (Ai,Bi)，求 X1,...,XN 满足：对于任意(A_i, B_i)，有 |XAi−XBi|=1 成立。

Special Judge

Input

第1行，2个整数N、M。
第2行到第 M+1 行，2个整数 Ai 和 Bi 。

Output

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

Sample Input

Input1：

3 3
1 2
2 3
3 1

Iuput2：

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

Sample Output

Input1：

NO

Input2：

YES
0 1 0 1 -99 -100

Data Constraint

对于40%的数据，1<=N<=10。
对于100%的数据，1<=N<=10,000，0<=M<=100,000，1<=Ai,Bi<=N。

Solution

• 可以发现答案可以只填两种数，如：1，2，2，1，1······

• 设数组 fi 表示答案序列（这里只填1或2）

• 即当 fi=1 时第 i 位填 1， fi=2 时第 i 位填 2，（fi=0 时表示第 i 位尚未填）

• 可以发现当两个点 x,y 有直接关系，则两点填的数互反。

• 即当 x 填 1 时，y 填 2；或当 x 填 2 时，y 填 1。

• 冲突当且仅当 fx，fy≠0 且 fx=fy

• 一直填到底若无冲突，即成功。

Code

#include<cstdio> using namespace std; int f[10001]; inline int read() {int data=0; char ch=0;while(ch<'0' || ch>'9') ch=getchar();while(ch>='0' && ch<='9') data=data*10+ch-'0',ch=getchar();return data; } int main() {int n=read(),m=read();for(int i=1;i<=m;i++){int x=read(),y=read();if(!f[x] && !f[y]){f[x]=1;f[y]=2;continue;}if(f[x]==f[y]){printf("NO");return 0;}if(!f[x]) f[x]=3-f[y];if(!f[y]) f[y]=3-f[x];}printf("YES\n");for(int i=1;i<=n;i++) printf("%d ",f[i]);return 0; }

总结

以上是生活随笔为你收集整理的JZOJ 4822. 【NOIP2016提高A组集训第1场10.29】完美标号的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。