BOJ 1707分チャート

質問する

導入する

図論では、二分図とは、すべての頂点を赤と青に塗りますが、すべてのエッジを赤と青の頂点に塗ります.
問題を答えようと思ったが、結局問題の話しか聞いていなかったので、よく理解できなかったので探してみた.
それはより性質に近いようで、以下のように定義されている.

定義＃テイギ＃

説明:

考えは簡単だ.
頂点を2つのグループに分ける場合、グループ内には幹線がありません.その名の通り、二部図です.

例えば、赤/緑の点の間には接続されていません.
定義によれば、可能なパケット化方法がある場合は、二分図である.

適用

では、どのようにしてプログラムを通じて実現するのでしょうか.
BFS、DFSなどを検索し、出会った人ごとに隣接する頂点とは反対の色を塗ります.
探索中に色を塗ったやつに出会ったら、塗る色とは逆?それは正義に対する矛盾だ.
したがって、このグラフは二分図ではありません.
このような判別方法で体現すればよい.

コード#コード#

// 2021.12.29 22:50:44
// 1707 https://boj.kr/1707
#include <bits/stdc++.h>
using namespace std;
#define RED 1
#define GREEN 2
#define VERTEX_MAX 20'001
#define EDGE_MAX 200'001

vector<vector<int>> edges(EDGE_MAX, vector<int>());
int visited[VERTEX_MAX];

int invertColor(int color)
{
    return color == RED ? GREEN : RED;
}

bool dfs(int vertex, int color)
{
    visited[vertex] = color;

    for (int next : edges[vertex])
    {
        if (visited[next] == color)
            return false;
        if (!visited[next] && !dfs(next, invertColor(color)))
            return false;
    }
    return true;
}

void init()
{
    for (int i = 1; i < EDGE_MAX; i++)
        edges[i].clear();
    for (int i = 1; i < VERTEX_MAX; i++)
        visited[i] = 0;
}

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int k;
    cin >> k;
    while (k--)
    {
        int v, e;
        cin >> v >> e;

        init();
        for (int i = 0; i < e; i++)
        {
            int v1, v2;
            cin >> v1 >> v2;
            edges[v1].push_back(v2);
            edges[v2].push_back(v1);
        }
        bool ret = true;
        for (int i = 1; i <= v; i++)
        {
            if (!visited[i] && !(ret = dfs(i, RED)))
                break;
        }
        cout << (ret ? "YES" : "NO") << '\n';
    }
}

初期化の問題でシャベルをよく使います.
初期化に気をつけて...

リファレンス

Wikipedia