UVa10505 - Montesco vs Capuleto(DFS、塗色問題)

題目大意

羅密歐與茱麗葉要結婚啦，但他們的雙方家庭是世仇，但他們還是希望可以找雙方家庭的親朋好友來，因此它們避免婚禮之間有衝突，他們邀請的人如下

• 如果 a 跟 b 是敵人，b 跟 c 也是敵人，d 跟 a,b,c 都不是敵人，那麼 a 跟 c 就是朋友、a 與 d 並不是朋友。
• 如果 a 跟 b 是敵人，雙方都討厭對方
• 我們只邀請數字小於 N 的人，大於 N 的都不邀請
• 如果我們邀請 a，那麼 a 以外的所有朋友都要參加，避免被誤會。

現在請告訴羅密歐與茱麗葉，最多有幾個人可以來參加婚禮

題目連結

重點觀念

• 塗色問題(在題目的第一點可以得知)

分析

• 寫一個 DFS，並分成 A、B 陣營，只要是 B 的敵人就是 A 陣營，反之亦同。
• 必須邀請每一個朋友，因此只要有一個好朋友不能來就不行，也表示當塗色問題遇到衝突時，就果斷放棄那棵樹，因為不管怎麼選都會有一個朋友沒辦法參加，或出現一個敵人。
  • 舉例，A 跟 B 是敵人、B 跟 C 是敵人、A 跟 C 是敵人
• 因此這個朋友關係表不可以有任何衝突，有就不能記錄
• 最多邀請人數 = 每一個朋友關係表中的最大陣營(max(a,b))
  每一個是因為題目不一定只給一個
• 紀錄，不可以發現衝突就 return 回來，這樣那一個完整的朋友關係圖沒有完整走過，因此我們不斷在尋找下一張朋友關系圖時，程式會拆成兩張，造成 bug

參考連結

Uva10505 - Montesco vs Capuleto by txya900619

心得

一開始我還沒辦法發現這是塗色問題QQ，加上好久沒有看到 if, and only if,，都是看到 iff，直接把題目意思給搞錯了…。

題目程式碼

會在下面放一些簡單註解，供大家學習時參考。

#include <iostream>
#include <bits/stdc++.h>
#define LOCAL
#define int long long
#define MAXN 300
using namespace std;
vector<int> edge[MAXN];
int visit[MAXN];
int t, n, cnt, enemy;
int color[2], flag; //color = A、B 兩大陣營，flag 為判斷這個朋友關係表是否有衝突

void dfs(int root, int status){ //status 表示現在的 node 必須是哪個陣營
    //cout << "root " << root << "\n";
    if(visit[root] == -1) visit[root] = status; //加入陣營
    else{
        //如果此節點已經有加入陣營且陣營與 status 相同，表示不衝突
        //注意這裡是用 and (1 & 1 = 0) (0 & 0=1)，不要像我一樣突然把 and 當成 nor..
        flag &= (visit[root] == status); 
        return; //他之前已經遍地過因此 return
    }

    //cout << "root status " << root << " " << visit[root] << "\n";
    color[status]++; //status 陣營增加一個
    for(int i = 0; i < edge[root].size(); i++){ //幫 subnode 加入敵對陣營
        dfs(edge[root][i], 1-status);
    }
    return;
}

int32_t main()
{
#ifdef LOCAL
    freopen("in1.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
#endif // LOCAL
    cin >> t;
    while(t--){
        cin >> n;
        for(int i = 1; i <= n; i++){
            visit[i] = -1;
            edge[i].clear();
        }

        for(int i = 1; i <= n; i++){
            cin >> cnt;
            for(int j = 0; j < cnt; j++){
                cin >> enemy;
                if(enemy > n) continue; //題目第三點說明
                edge[i].push_back(enemy); //雙向，題目第二點說明
                edge[enemy].push_back(i);
                //cout << "i enemy " << i << " " << enemy << "\n";
            }
        }

        int ans = 0;
        for(int i = 1; i <= n; i++){
            memset(color, 0, sizeof(color));
            if(visit[i] == -1){
                flag = 1;
                dfs(i, 0); 
                //表示這個朋友關係表沒有衝突，找最大的陣營的來參加婚禮
                if(flag == 1) ans += max(color[0], color[1]); 
            }

            //cout << "max " << max(color[0], color[1]) << "\n";
        }
        cout << ans << "\n";
    }

    return 0;
}