F. Graph Without Long Directed Paths

刺骨的言语ヽ痛彻心扉 2022-02-25 11:40 150阅读 0赞

### 题目描述： ###

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  
Copy

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

Output  
Copy

YES  
10100

Note

The picture corresponding to the first example:  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNTA2MTM4_size_16_color_FFFFFF_t_70]  
And one of possible answers: ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNTA2MTM4_size_16_color_FFFFFF_t_70 1]

##### 题意： #####

本题题意有点难以理解。  
给你一个无向图，让你把这个图变成有向图。  
这个有向图需要满足的是，从每一个结点出发到另一个结点。只能有一个路径长度。  
通俗讲，就是，如果A 结点 有一条路径到B 结点，那么B 结点就不能再有其他路径到其他结点去了。

分析：  
这是一个染色题目吧。我们可以设只有出度的结点为1，只有入度的结点为0。  
如果A结点为1，那么与A相连的结点只能为0。如果，这样建完图后，有相连的结点都是1或者0的话，那么输出NO。 否则YES。

#include"string.h"
    #include"functional"
    #include"iostream"
    #include"vector"
    #include"algorithm"
       using namespace std;
    typedef long long ll;
    #define scanll(a,b) scanf("%I64d%I64d",&a,&b);
    #define scanl(a) scanf("%I64d",&a);
    #define scanff(a,b) scanf("%lf%lf",&a,&b);
    #define scan1f(a) scanf("%lf",&a);
    #define prinll(a,b) printf("%I64d %I64d",a,b);
    #define prinl(a) printf("%I64d",a);
    #define printff(a,b) printf("%lf %lf",a,b);
    #define printlf(a) printf("%lf",a);
    vector<ll> Q[200010];
    ll vis[200010];
    ll id[200010];
    ll path[200010][2];
    void dfs(ll step,ll K)
    {
        for(ll i=0;i<Q[step].size();i++)
        {
            if(vis[Q[step][i]]==0)
            {
                vis[Q[step][i]]=1;
                id[Q[step][i]]=!K;
                dfs(Q[step][i],!K);
            }
        }
    }
    int main()
    {
        ll n,m;
        scanll(n,m);
        for(ll i=1;i<=m;i++)
        {
            ll a,b;
            scanll(a,b);
            Q[a].push_back(b);
            Q[b].push_back(a);
            path[i][0]=a;path[i][1]=b;
        }
        id[1]=0;
        vis[1]=1;
        dfs(1,0);//相连的结点的属性必不同。
        ll flat=1;
        for(ll i=1;i<=m;i++)
        {
            if(id[path[i][0]]==id[path[i][1]])//如果相连结点的属性相同了。则NO
            {
                flat=0;
                printf("NO\n"); return 0;
            }
        }
        printf("YES\n");
        for(ll i=1;i<=m;i++)
        {
            if(id[path[i][0]]==1&&id[path[i][1]]==0)
                printf("1");
            else
                printf("0");
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNTA2MTM4_size_16_color_FFFFFF_t_70]: /images/20220225/39290295e816479f833431de3d048039.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNTA2MTM4_size_16_color_FFFFFF_t_70 1]: /images/20220225/7cc33c4216ac48849bdc6370eb084da7.png