【題解】TIOJ 2062 . 分點問題(一)

【範例】二分圖判定
【題目敘述】https://tioj.ck.tp.edu.tw/problems/2062
【解題想法】二分圖染色(BFS)

  • c[ i ]:第 i 個點的分類
    • 0 表示尚未被分類
    • 1 表示塗上第一種顏色
    • -1表示塗上第二種顏色
  • (Line-20) 枚舉所有點,確保所有的連通塊都會被處理。
  • (Line-21) 全新的連通塊中號碼最小的,先塗 1。
  • queue裡面存放的都是已經塗過顏色的點
    • 相鄰已塗色的點,如果顏色與now相同,則不是二分圖。
    • 遇到相鄰但尚未塗色的點,塗上另一種顏色。
#include <iostream>
#include <vector>
#include <queue>
using namespace std;

const int maxn = 1000005;
int n, m, x, y, c[maxn];
vector <int> g[maxn], a, b;
queue <int> q;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m;
    for (int i = 0; i < m; i++){
        cin >> x >> y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    for (int i = 1; i < n; i++){
        if (c[i]) continue;
        c[i] = 1;
        q.push(i);
        while (!q.empty()){
            int now = q.front();
            q.pop();
            if (c[now] == 1) a.push_back(now);
            else b.push_back(now);
            for (int j:g[now]){
                if (c[j]){
                    if (c[j] == c[now]){
                        cout << "-1\n";
                        return 0;
                    }
                }
                else {
                    c[j] = -c[now];
                    q.push(j);
                }
            }
        }
    }
    cout << a.size() << " " << b.size() << "\n";
    for (int i:a){
        cout << i << " ";
    }
    cout << "\n";
    for (int i:b){
        cout << i << " ";
    }
    cout << "\n";
}
分享本文 Share with friends