[AOJ] No. 0321 部活動調査

2019年12月29日2020年12月17日

問題

方針

各生徒をノードに見立てて、隣接リストを構築します。生徒 \( i \) が所属している部活動を \( g_i \) とし、所属が未確定のときを \( g_i = 0 \) とします。生徒 \( a, b \) が同じ部活動に所属しているという情報から、

\[ g_a \neq g_b \wedge g_a \neq 0 \wedge g_b \neq 0\]

のとき校則に違反していることになります。また、\( g_a \neq 0\) または \( g_b \neq 0 \) のとき、生徒 \( a, b \) の隣接リストを走査して校則に違反しているかどうかを調べます。これは、幅優先探索を行うことで実現できます。

つぎに、生徒 \( c \) が部活動 \( x \) に所属しているという情報から、生徒 \( c \) の隣接リストを走査します。

コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
    int N, M, K;
    cin >> N >> M >> K;
    vector<int> adj[N];
    int r[K][3]{};
    for (int i = 0; i < K; i++) {
        cin >> r[i][0] >> r[i][1] >> r[i][2];
        if (r[i][0] == 1) {
            r[i][1]--;
            r[i][2]--;
        } else {
            r[i][1]--;
        }
    }
    int g[N]{};
    for (int i = 0; i < K; i++) {
        if (r[i][0] == 1) {
            int a = r[i][1];
            int b = r[i][2];
            if (g[a] != 0 && g[b] != 0 && g[a] != g[b]) {
                cout << i + 1 << "\n";
                return 0;
            }
            adj[r[i][1]].push_back(r[i][2]);
            adj[r[i][2]].push_back(r[i][1]);
            deque<int> q;
            if (g[a] != 0 && g[b] == 0) {
                g[b] = g[a];
                q.push_back(a);
            }
            if (g[b] != 0 && g[a] == 0) {
                g[a] = g[b];
                q.push_back(b);
            }
            int x = g[a];
            while (!q.empty()) {
                int u = q.front();
                q.pop_front();
                for (int j = 0; j < adj[u].size(); j++) {
                    int v = adj[u][j];
                    if (g[v] == 0) {
                        g[v] = x;
                        q.push_back(v);
                    } else if (g[v] != x) {
                        cout << i + 1 << "\n";
                        return 0;
                    }
                }
            }          

        } else {
            int c = r[i][1];
            int x = r[i][2];
            if (g[c] != 0 && g[c] != x) {
                cout << i + 1 << "\n";
                return 0;
            }
            g[c] = x;
            deque<int> q;
            q.push_back(c);
            while (!q.empty()) {
                int u = q.front();
                q.pop_front();
                for (int j = 0; j < adj[u].size(); j++) {
                    int v = adj[u][j];
                    if (g[v] == 0) {
                        g[v] = x;
                        q.push_back(v);
                    } else if (g[v] != x) {
                        cout << i + 1 << "\n";
                        return 0;
                    }
                }
            }
        }
    }
    cout << "0\n";
    return 0;
}