526互联

Codeforces Round 550 (Div. 3) F. Graph Without Long Directed Paths（dfs/染色）

发布时间 2023-04-20 18:12:04作者: 高尔赛凡尔娟

https://codeforces.com/contest/1144/problem/F

题目大意：

给定n个点，m条边；

每一条边都连接了两个点。

现在需要我们染色，要求是做到所有有向图不包含长度为2或者更长的路径。

input 
6 5
1 5
2 1
1 4
3 1
6 1
output 
YES
10100

详解见代码内部注释部分

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL,LL> PII;
const LL MAXN=1e18;
const LL N=1e6,M=4002;
LL n,m;
vector<LL> g[N];
LL col[N],vis[N];
map<LL,PII> mp;
void dfs(LL idx,LL color)
{
    for(int i=0;i<g[idx].size();i++)
    {
        //如果没有染过颜色的
        if(vis[g[idx][i]]==0)
        {
            vis[g[idx][i]]=1;
            col[g[idx][i]]=!color;//染一下相反的颜色
            dfs(g[idx][i],!color);//继续往下染色
        }
    }
}
int main()
{
    //cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
    LL T=1;
    //cin>>T;
    while(T--)
    {
        cin>>n>>m;
        for(int i=1;i<=m;i++)
        {
            LL a,b;
            cin>>a>>b;
            //双向边
            g[a].push_back(b);
            g[b].push_back(a);
            //mp存储第i条边的左边节点和右边节点
            mp[i].first=a;
            mp[i].second=b;
        }
        //从1开始染色，经过了1点标注一下
        //如果是有向边的起点我们染色为0，否则染色为1
        col[1]=0,vis[1]=1;
        dfs(1,0);
        bool flag=true;
        for(int i=1;i<=m;i++)
        {
            //如果左边右边都染成了一样的颜色，那肯定就是不行的
            if(col[mp[i].first]==col[mp[i].second])
            {
                flag=false;
                cout<<"NO"<<endl;
                return 0;
            }
        }
        cout<<"YES"<<endl;
        for(int i=1;i<=m;i++)
        {
            //左边染色为1，右边染色为0，可以染色为0（0向1指向方向）
            if(col[mp[i].first]==1&&col[mp[i].second]==0) cout<<"0";
            else cout<<"1";
        }
    }
    return 0;
}