AIM Tech Round (Div. 2) C. Graph and String 二分图染色
C. Graph and String
题目连接:
http://codeforces.com/contest/624/problem/C
Description
One day student Vasya was sitting on a lecture and mentioned a string s1s2... sn, consisting of letters "a", "b" and "c" that was written on his desk. As the lecture was boring, Vasya decided to complete the picture by composing a graph G with the following properties:
G has exactly n vertices, numbered from 1 to n.
For all pairs of vertices i and j, where i ≠ j, there is an edge connecting them if and only if characters si and sj are either equal or neighbouring in the alphabet. That is, letters in pairs "a"-"b" and "b"-"c" are neighbouring, while letters "a"-"c" are not.
Vasya painted the resulting graph near the string and then erased the string. Next day Vasya's friend Petya came to a lecture and found some graph at his desk. He had heard of Vasya's adventure and now he wants to find out whether it could be the original graph G, painted by Vasya. In order to verify this, Petya needs to know whether there exists a string s, such that if Vasya used this s he would produce the given graph G.
Input
The first line of the input contains two integers n and m — the number of vertices and edges in the graph found by Petya, respectively.
Each of the next m lines contains two integers ui and vi (1 ≤ ui, vi ≤ n, ui ≠ vi) — the edges of the graph G. It is guaranteed, that there are no multiple edges, that is any pair of vertexes appear in this list no more than once.
Output
In the first line print "Yes" (without the quotes), if the string s Petya is interested in really exists and "No" (without the quotes) otherwise.
If the string s exists, then print it on the second line of the output. The length of s must be exactly n, it must consist of only letters "a", "b" and "c" only, and the graph built using this string must coincide with G. If there are multiple possible answers, you may print any of them.
Sample Input
2 1
1 2
Sample Output
Yes
aa
Hint
题意
给你一个图,然后让你给这些图标号,问你有没有一个合法的标号
标号就只能标a,b,c。
然后a会和ab连边,b和abc都连边,c和bc连边
有解就任意输出一个就好
题解:
我们首先把那种边集有n-1的点染成b,然后再随便选一个没有染成b的点当成a,然后和a连边的就是a,没有和a连边的就是c
扫一遍就可以确认所有点的颜色,最后再n^2check一发就好了
代码
#include<bits/stdc++.h>
using namespace std;
int mp[520][520];
int cnt[520];
int flag[520];
int n,m;
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
int x,y;
scanf("%d%d",&x,&y);
mp[x][y]=1;
mp[y][x]=1;
cnt[x]++;
cnt[y]++;
}
for(int i=1;i<=n;i++)
if(cnt[i]==n-1)
flag[i]=2;
int now=0;
for(int i=1;i<=n;i++)
if(flag[i]!=2)
{
now=i;
break;
}
if(now==0)
{
printf("Yes\n");
for(int i=1;i<=n;i++)
cout<<"b";
cout<<endl;
return 0;
}
flag[now]=1;
for(int i=1;i<=n;i++)
{
if(now==i)continue;
if(!mp[i][now])flag[i]=3;
else if(flag[i]==0)flag[i]=1;
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(i==j)continue;
if(mp[i][j])
{
if(abs(flag[j]-flag[i])>1)
return puts("No");
}
else
{
if(abs(flag[j]-flag[i])<=1)
return puts("No");
}
}
}
printf("Yes\n");
for(int i=1;i<=n;i++)
if(flag[i]==1)printf("a");
else if(flag[i]==2)printf("b");
else printf("c");
printf("\n");
}
最新文章
- webservice 测试窗体只能用于来自本地计算机的请求
- Kernel Methods (5) Kernel PCA
- JS判断客户端是手机还是PC的2个代码(转)
- 修改placeholder提示内容的颜色以及文本框输入文字内容的颜色
- windows 程序设计自学:添加字符串资源
- 洛谷P2925 [USACO08DEC]干草出售Hay For Sale
- 在C#中怎么调用带参数的存储过程啊??
- NeHe OpenGL教程 第三课:颜色渲染
- [Bootstrap]组件(三)
- Eclipse 调整代码颜色的地方
- iOS-设计模式之通知
- google base 之MessagePumpForUI
- JS对select动态添加option操作 (三级联动) (搜索拼接)
- Docker打包 Asp.Net Core应用,在CentOS上运行
- 〖Linux〗Kubuntu设置打开应用时就只在打开时的工作区显示
- MyBatis学习笔记(四)——解决字段名与实体类属性名不相同的冲突
- c++第十七天
- 集合由量大接口派生来:Collection 和 Map
- opencv学习笔记——FileStorage类的数据存取操作
- python中的MRO和C3算法
热门文章
- C++模板知识小结
- 通过HttpClient来调用Web Api接口
- As3 计算两个日期之间的天数差
- 网站压力测试工具-Webbench源码笔记
- 配置Texmaker中文支持
- Window.onLoad 和 DOMContentLoaded事件的先后顺序
- 获取子窗口中使用jQuery.data()设置的参数
- [POJ] #1007# DNA Sorting : 桶排序
- [转] 苹果所有常用证书,appID,Provisioning Profiles配置说明及制作图文
- Shell脚本文件中常用的操作语句