2020NYIST个人积分赛第九场F题CF1144F

文章目录[x]
  1. 1:2020NYIST个人积分赛第九场F题
  2. 2:原题链接
  3. 3:题意
  4. 4:思路
  5. 5:参考代码

csdn链接:https://nuoyanli.blog.csdn.net/article/details/105695497




2020NYIST个人积分赛第九场F题

原题链接

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

题意

给你一个无向图,让你把所有边标记方向,并使其没有距离的边,问你是否存在并输出方案。

思路

距离大于等于2,可不就是分成两个点集, ,使得只存在从 的边,不存在回来的边,显然就是二分图(Orz),还是图论做少了,就很的二分图染色。

枚举点,染色黑白点之间随便定一个方向,可以黑到白也可以白到黑。
即可。

参考代码

// nuoyanli
#include <algorithm>
#include <cmath>
#include <queue>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <vector>
#include <iostream>
using namespace std;
#define IOS ios::sync_with_stdio(false), cin.tie(0)
#define endl '\n'
#define kB kush_back
#define FI first
#define SE second
//#define in
#define RI register
#define m_k(a, b) make_pair(a, b)
#define PB(a) push_back(a)
#define debug(a) cout << "---" << a << "---" << endl
#define debug_(a, b) cout << a << "---" << b << endl
#define bl(x) setiosflags(ios::fixed) << setprecision(x)
const double pi = acos(-1.0);
const double eps = 1e-9;
typedef long long LL;
const int N = 1e6 + 10;
const int M = 1e3 + 10;
const LL mod = 1e9 + 7;
const LL inf = 1e18;
const double f = 0.32349;
vector <int> G[N];
int n, m, col[N];
bool vs = 0;
void dfs(int u, int c) {
    col[u] = c;
    for (auto v:G[u]) {
        if (col[v] == -1) {//没有染过色
            dfs(v, c ^ 1);//染上与现在不同的颜色
        } else if (col[v] == c) { //有一个点已经染色且与当前点颜色相同
            vs =1;
            return;
        }
    }
}
vector <pair <int, int> >Edges;
int main() {
    IOS;
    cin >> n >> m;
    for(int i=0; i<m; i++) {
        int u, v;
        cin >> u >> v;
        --u, --v;//从0开始编号
        G[u].PB(v);
        G[v].PB(u);
        Edges.PB(m_k(u, v));
    }
    memset(col, -1, sizeof(col));//-1表示没有染过色
    dfs(0, 0);
    if(vs) {
        cout<<"NO"<<endl;
    } else {
        cout << "YES" << endl;
        for (auto i:Edges) {
            if (col[i.FI] == 0)cout << 1;
            else cout << 0;
        }
    }
    return 0;
}


点赞

发表评论

昵称和uid可以选填一个,填邮箱必填(留言回复后将会发邮件给你)
tips:输入uid可以快速获得你的昵称和头像