2 seconds
256 megabytes
standard input
standard output
You are given a connected undirected graph consisting of nn vertices and mm edges. There are no self-loops or multiple edges in the given graph.
You have to direct its edges in such a way that the obtained directed graph does not contain any paths of length two or greater (where the length of path is denoted as the number of traversed edges).
The first line contains two integer numbers nn and mm (2≤n≤2⋅1052≤n≤2⋅105, n−1≤m≤2⋅105n−1≤m≤2⋅105) — the number of vertices and edges, respectively.
The following mm lines contain edges: edge ii is given as a pair of vertices uiui, vivi (1≤ui,vi≤n1≤ui,vi≤n, ui≠viui≠vi). There are no multiple edges in the given graph, i. e. for each pair (ui,viui,vi) there are no other pairs (ui,viui,vi) and (vi,uivi,ui) in the list of edges. It is also guaranteed that the given graph is connected (there is a path between any pair of vertex in the given graph).
If it is impossible to direct edges of the given graph in such a way that the obtained directed graph does not contain paths of length at least two, print "NO" in the first line.
Otherwise print "YES" in the first line, and then print any suitable orientation of edges: a binary string (the string consisting only of '0' and '1') of length mm. The ii-th element of this string should be '0' if the ii-th edge of the graph should be directed from uiui to vivi, and '1' otherwise. Edges are numbered in the order they are given in the input.
6 5
1 5
2 1
1 4
3 1
6 1
YES
10100 这个题的题意就是修改一些边的方向让有向图不包含长度为2或更大的任何路径(其中路径长度表示为遍历边的数量),修改的边标记为1,没修改的标记为0,最后按顺序输出所有的边的标记
如下图
思路在下面代码的注释中
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<algorithm>
using namespace std;
const int maxn=2e5+;
const int inf=0x3f3f3f3f;
int n,m;
int first[maxn],sign;
int vis[maxn];
int a[maxn][];
struct node
{
int to,w,next;
} edge[maxn<<];
void init()
{
for(int i = ; i <=n; i++)
first[i]=-;
sign=;
}
void add_edge(int u,int v,int w)
{
edge[sign].to=v;
edge[sign].w=w;
edge[sign].next=first[u];
first[u]=sign++;
}
bool flag1=;
void dfs(int x,int flag)///对整个图进行染色1 0 1 0...,
{
vis[x]=flag;
for(int i=first[x]; ~i; i=edge[i].next)
{
int to=edge[i].to;
if(vis[to]==vis[x])///判断是是否有环
{
flag1=;
return ;
}
if(vis[to]==-)
{
dfs(to,flag^);
}
}
return ; }
int main()
{
scanf("%d%d",&n,&m);
init();
for(int i=; i<=m; i++)
{
int u,v;
scanf("%d%d",&u,&v);
add_edge(u,v,);
add_edge(v,u,);
a[i][]=u;
a[i][]=v;
}
memset(vis,-,sizeof(vis));
dfs(,);
if(flag1)
puts("NO");///如果图中有环的话,肯定就会存在dist>=2的点,可以自己画一个三角形看看,就很容易理解了
else
{
puts("YES");
for(int i=; i<=m; i++)
{
if(vis[a[i][]]==)///a[i][0]为第i条边的起点,a[i][1]为第i条边的终点。
///这里我们已经将整个图染色,整个图分为两类,标记为1的点和标记为0的点
///以标记为1的点为起点,出发的边不做修改,即边的标记为0
///以标记为0的点为起点,出发的边改为相反的方向,即边的标记为1,
///这里其实是不难理解的,两个相邻的点必定为1 0或者0 1,1->0->1
///(1出发的边保持原来的方向,0出发的边改为相反的方向)或者(0出发
///的边保持原来的方向,1出发的边改为相反的方向)才能使得整个图的不出现长度为2或者更大的路径
printf("");
else
printf("");
}
} return ;
}
Codeforces Round #550 (Div. 3) F. Graph Without Long Directed Paths的更多相关文章
-
Codeforces Round #550 (Div. 3) F. Graph Without Long Directed Paths (二分图染色)
题意:有\(n\)个点和\(m\)条无向边,现在让你给你这\(m\)条边赋方向,但是要满足任意一条边的路径都不能大于\(1\),问是否有满足条件的构造方向,如果有,输出一个二进制串,表示所给的边的方向 ...
-
Codeforces Round #496 (Div. 3) F - Berland and the Shortest Paths
F - Berland and the Shortest Paths 思路:还是很好想的,处理出来最短路径图,然后搜k个就好啦. #include<bits/stdc++.h> #defi ...
-
F. Graph Without Long Directed Paths Codeforces Round #550 (Div. 3)
F. Graph Without Long Directed Paths time limit per test 2 seconds memory limit per test 256 megabyt ...
-
Codeforces Round #485 (Div. 2) F. AND Graph
Codeforces Round #485 (Div. 2) F. AND Graph 题目连接: http://codeforces.com/contest/987/problem/F Descri ...
-
Codeforces Round #486 (Div. 3) F. Rain and Umbrellas
Codeforces Round #486 (Div. 3) F. Rain and Umbrellas 题目连接: http://codeforces.com/group/T0ITBvoeEx/co ...
-
Codeforces Round #501 (Div. 3) F. Bracket Substring
题目链接 Codeforces Round #501 (Div. 3) F. Bracket Substring 题解 官方题解 http://codeforces.com/blog/entry/60 ...
-
Codeforces Round #499 (Div. 1) F. Tree
Codeforces Round #499 (Div. 1) F. Tree 题目链接 \(\rm CodeForces\):https://codeforces.com/contest/1010/p ...
-
CodeForces Round #550 Div.3
http://codeforces.com/contest/1144 A. Diverse Strings A string is called diverse if it contains cons ...
-
Codeforces Round #375 (Div. 2) F. st-Spanning Tree 生成树
F. st-Spanning Tree 题目连接: http://codeforces.com/contest/723/problem/F Description You are given an u ...
随机推荐
-
CSS 滤镜(IE浏览器专属其他浏览器不支持)
Filter 属性介绍: 设置或检索对象所应用的滤镜或滤镜集合.此属性仅作用于有布局的对象,如块对象.内联要素要使用该属性,必须先设定对象的 height 或 width 属性,或者设定 positi ...
-
鼠标指向GridView某列显示DIV浮动列表
需求: 当GRIDVIEW数据列过多,不方便全部显示在同一行或者一些子信息需要鼠标指向某关键列GRIDVIEW的时候显示其子信息. 设计:先把需要显示的浮动数据一次过抓取出来.而不是鼠标指向的时候才从 ...
-
MSP430看门狗
其实430的看门狗,与51的大同小异,都是为了防止程序跑飞而出现不可预知的错误而专门设定的,所以说,看门狗的应用,是项目马上要进行实际应用中必须要进行的一环,也是电子工程师必须掌握的一环,下面介绍一下 ...
-
jsp查询页面和结果页面在同一页面显示和交互
用frameset实现查询页面和结果页面在同一页面 用target实现交互显示在同一页面上 请参照以下方法解决: main.jsp: <html> <head> <met ...
-
(转载)PHP array_slice() 函数
(转载)http://www.w3school.com.cn/php/func_array_slice.asp PHP Array 函数 定义和用法 array_slice() 函数在数组中根据条件取 ...
-
Android中的跨进程通信方法实例及特点分析(二):ContentProvider
1.ContentProvider简单介绍 在Android中有些数据(如通讯录.音频.视频文件等)是要供非常多应用程序使用的.为了更好地对外提供数据.Android系统给我们提供了Content P ...
-
SQL Server 日期相关
原文:SQL Server 日期相关 原帖出处:http://blog.csdn.net/dba_huangzj/article/details/7657979 对于开发人员来说,日期处理或许简单,或 ...
-
Spring4托管Hibernate5并利用HibernateTemplate进行数据库操作
时隔半年,再次发布配置类的相关Blog,因为左手受伤原因先做一个简述. 首先利用idea创建一个Spring+SpringMVC+Hibernate项目,注意的是因为我们要完全放弃Hibernate以 ...
-
Unity打包提示UnityEditor.BuildPlayerWindow+BuildMethodException: Build failed with errors.错误
不要将打包的输出路径设置为Assets文件夹下面即可,MD真坑 老外给出的解释: As you have noticed after you click build settings you are ...
-
mui 下拉刷新和上拉加载
<body> mui文档提供了两种不同模式的下拉刷新,具体情况看文档,链接:http://dev.dcloud.net.cn/mui/pulldown/ 单 webview 模式和 双 w ...