bipartite_graph.cpp

Bài toán

Kiểm tra một đồ thị vô hướng có phải là hai phía.

Độ phức tạp

O(n+m)

Code này của Nguyễn Tiến Trung Kiên

#include <stdio.h>

#include <vector>

#include <iostream>

#include <algorithm>

using namespace std;

int n, m;

vector<int> a[12309];

bool Invalid = false;

bool Visited[12309];

int Color[12309];

void visit(int u) {

    Visited[u] = true;

    for (int i = 0; i < a[u].size(); i++) {

        int v = a[u][i];

        if (!Visited[v]) {

            Color[v] = 3 - Color[u];

            visit(v);

        }

        else {

            if (Color[v] == Color[u])

                Invalid = true;

        }

    }

}

int main() {

    cin >> n >> m;

    for (int i = 1; i <= m; i++) {

        int p, q;

        cin >> p >> q;

        a[p].push_back(q);

        a[q].push_back(p);

    }

    for (int i = 1; i <= n; i++) {

        if (!Visited[i]) {

            Color[i] = 1;

            visit(i);

        }

    }

    if (Invalid)

        cout << "Invalid" << endl;

    else {

        for (int i = 1; i <= n; i++) cout << Color[i] << " ";

        cout << endl;

    }

}

Nhận xét