Uva10505 - Montesco vs Capuleto

題目大意

有一對新人想舉辦婚禮，但他們的朋友之中有些關係不太好，我們要找到關係良好且最多的人數

重點觀念

• dfs
• 塗色

分析

• 給這些人塗色，若有提對關係則為另一個顏色，遇到衝突的顏色時跳開

程式題目碼

#include <iostream>
#include <vector>

using namespace std;

vector<int> graph[300];
int color[300];

void dfs(int cur, int cur_color, int& A, int& B, bool& flag) {
    if (color[cur] != -1)
        flag &= (color[cur] == cur_color);
    else {
        color[cur] = cur_color;
        A++;
        for (auto i = graph[cur].begin(); i != graph[cur].end(); i++)
            dfs(*i, 1 - cur_color, B, A, flag);
    }
}

int main() {
    int M;
    cin >> M;

    while (M--) {
        int N;
        cin >> N;
        for (int i = 0; i < N; i++) {
            color[i] = -1;
            graph[i].clear();
        }
        for (int i = 0; i < N; i++) {
            int p;
            cin >> p;
            for (int j = 0; j < p; j++) {
                int enemy;
                cin >> enemy;
                enemy--;
                if (enemy >= N) {
                    continue;
                }
                graph[i].push_back(enemy);
                graph[enemy].push_back(i);
            }
        }
        int ans = 0;
        for (int i = 0; i < N; i++) {
            if (color[i] == -1) {
                int A = 0;
                int B = 0;
                bool flag = true;
                dfs(i, 0, A, B, flag);
                if (flag) {
                    ans += max(A, B);
                }
            }
        }

        cout << ans << endl;
    }

    return 0;
}