F. Graph Without Long Directed Paths

Link

题解

题目要求给一个连通无向图中的所有边加上方向后使得整张图没有长度超过1的有向路径，如果图能二分，使从左往右的边为1从右往左的边为0（反过来亦可），如果不能二分则无论方向怎么分配必然存在长度大于等于2的有向路径所以输出NO。

二分图染色

代码

#include <algorithm>
#include <cmath>
#include <cstring>
#include <iostream>
#include <string>
#include <vector>
#define pii pair<int, int>
#define mpr make_pair
const int maxn = 2e5 + 10;
using namespace std;

vector<int>G[maxn];
int clr[maxn], flag;

void dfs(int x, int c) {
    clr[x] = c;
    for (auto i : G[x]) {
        if (clr[i] == -1)dfs(i, c ^ 1);
        else {
            if (clr[x] == clr[i])flag = 0;
        }
    }
}

int main() {
    int x, y, n, m;
    vector<pii>edges;
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        cin >> x >> y;
        --x, --y;
        G[x].push_back(y);
        G[y].push_back(x);
        edges.push_back(mpr(x, y));
    }
    for (int i = 0; i < n; i++)clr[i] = -1;
    flag = 1;
    dfs(0, 0);
    if (!flag)cout << "NO" << endl;
    else {
        cout << "YES" << endl;
        for (auto e : edges)cout << (clr[e.first] < clr[e.second]);
        cout << endl;
    }
    return 0;
}