Codeforces Round #550 (Div. 3) F. Graph Without Long Directed Paths

Codeforces Round #550 (Div. 3) F. Graph Without Long Directed Paths

原题链接：http://codeforces.com/contest/1144/problem/F

题目：

You are given a connected undirected graph consisting of n vertices and m 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).

Input
The first line contains two integer numbers n and m (2≤n≤2⋅105, n−1≤m≤2⋅105) — the number of vertices and edges, respectively.

The following m lines contain edges: edge i is given as a pair of vertices ui, vi (1≤ui,vi≤n, ui≠vi). There are no multiple edges in the given graph, i. e. for each pair (ui,vi) there are no other pairs (ui,vi) and (vi,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).

Output
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 m. The i-th element of this string should be ‘0’ if the i-th edge of the graph should be directed from ui to vi, and ‘1’ otherwise. Edges are numbered in the order they are given in the input.

Example
input
6 5
1 5
2 1
1 4
3 1
6 1
output
YES
10100
Note
The picture corresponding to the first example:

题意

给你一个图，改变其中任意条边的方向，使得图中不存在路径大于1的边。如果能做到，按边的输入顺序输出1/0（1代表你把边的方向变成反向，0代表边的方向不变）。如果不能做到，输出NO。
比如

就存在一条路径为2的边（A -> B -> C），不符合要求。
而下图只存在两条路径为1的边，符合要求。

思路

那么对于每一个点，应该只有出边或只有入边才符合要求。我们可以对点进行染色，由一条边连接起来的两点的染色不能相同。bfs就完事。
如果在染色过程中发现由边直接连接的两点染色相同，则直接输出NO。
（染色这个画个图就很好理解了）

代码

#include <bits/stdc++.h> 
typedef long long ll;
const int maxn = 2e5 + 5;
const int inf = 0x3f3f3f3f;
const double eps = 0.00001;
using namespace std;

int n, m;
struct node{
	int u, v;
}e[maxn];
int tag;
vector <int> vec[maxn];
int flag[maxn], vis[maxn];
void bfs(){
	queue <int> q;
	q.push(1);
	vis[1] = 1;
	flag[1] = 1;
	while(q.size()){
		int u = q.front();
		q.pop();
		flag[u] = 0;
		for(int i = 0; i < vec[u].size(); i++){
			int v = vec[u][i];
			if(vis[u] == vis[v]){//直接相连的点染色相同 
				tag = 1;
			}
			else if(vis[v])	continue;//点v已经染过色而且与u颜色不同 
			else{
				if(vis[u] == 1)	vis[v] = 2;
				else	vis[v] = 1;
				if(!flag[v]){
					flag[v] = 1;
					q.push(v);
				}
			}
		}
		if(tag)	break;
	}
} 
int main()
{
	memset(flag, 0, sizeof(flag));//判断该点是否在队列内 在队内=1， 不在对内=0 
	memset(vis, 0, sizeof(vis));//标记染色 有1 2两种颜色 
	cin >> n >> m;
	tag = 0;//判断相邻两个点染色是否相同，如果相同则为1 
	for(int i = 1; i <= n; i++)	vec[i].clear();
	for(int i = 0; i < m; i++){
		cin >> e[i].u >> e[i].v;
		vec[e[i].u].push_back(e[i].v);//vector里存的都是由边直接相连的点 
		vec[e[i].v].push_back(e[i].u);
	}
	bfs();
	if(tag){
		puts("NO");
		return 0;
	}
	puts("YES");
	for(int i = 0; i < m; i++){
		if(vis[e[i].u] == 1)	cout << 1;
		else	cout << 0;
	}
	cout << endl;
		
	
	return 0;
}