mayoko’s diary

プロコンとかいろいろ。

AtCoder Regular Contest 049 C - ぬりまーす

解法

タイプ 1 の制約は, 「y -> x という順番で塗る」という制約であると考えることが出来ます。順序関係は有向グラフで表せます。

タイプ 1 の制約しかないと考えた場合, 閉路があるところを除いてすべての頂点を通ることが出来ます。これは強連結成分分解を使うと簡単です(強連結成分に複数の頂点がある場合はそれらの頂点は通らない)。

タイプ 2 の制約についてもこんな感じで有向グラフで表したいですが, そう出来ます。具体的には,

  • u -> v と通る
  • u は絶対通らない

の 2 通りに分けて, 2^B 通り調べれば良いです。

struct SCC {
    int V;
    vector<vi> G, rG;
    vector<int> vs, used, cmp;
    SCC(const vector<vi>& g) : V(g.size()), G(g), rG(V), used(V), cmp(V) {
        for (int i = 0; i < V; i++) for (int u : G[i]) rG[u].push_back(i);
    }
    void dfs(int v) {
        used[v] = 1;
        for (int u : G[v]) if (!used[u]) dfs(u);
        vs.push_back(v);
    }
    void rdfs(int v, int k) {
        used[v] = 1;
        cmp[v] = k;
        for (int u : rG[v]) if (!used[u]) rdfs(u, k);
    }
    int calc() {
        fill(used.begin(), used.end(), 0);
        vs.clear();
        for (int v = 0; v < V; v++) {
            if (!used[v]) dfs(v);
        }
        fill(used.begin(), used.end(), 0);
        int k = 0;
        for (int i = vs.size()-1; i >= 0; i--) {
            if (!used[vs[i]]) rdfs(vs[i], k++);
        }
        return k;
    }
};

const int MAX = 110;
int N, A, B;
int X[MAX], Y[MAX], U[MAX], V[MAX];

bool NG[MAX];

void dfs(int v, const vector<vi>& G) {
    NG[v] = true;
    for (int u : G[v]) {
        if (!NG[u]) dfs(u, G);
    }
}

int calc(int state) {
    memset(NG, false, sizeof(NG));
    vector<vi> G(N), rG(N);
    vector<int> degree(N, 0);
    for (int i = 0; i < A; i++) {
        G[Y[i]].push_back(X[i]);
        rG[X[i]].push_back(Y[i]);
    }
    for (int i = 0; i < B; i++) {
        if (state%2 == 0) {
            G[U[i]].push_back(V[i]);
            rG[V[i]].push_back(U[i]);
        } else {
            NG[U[i]] = true;
        }
        state /= 2;
    }
    SCC scc(G);
    int k = scc.calc();
    vector<vi> comp(k);
    for (int i = 0; i < N; i++) comp[scc.cmp[i]].push_back(i);
    for (int i = 0; i < k; i++) {
        if (comp[i].size() > 1) for (int v : comp[i]) NG[v] = true;
    }
    for (int i = 0; i < N; i++) if (NG[i]) dfs(i, G);
    int ans = N;
    for (int i = 0; i < N; i++) if (NG[i]) ans--;
    return ans;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> N;
    cin >> A;
    for (int i = 0; i < A; i++) {
        cin >> X[i] >> Y[i];
        X[i]--; Y[i]--;
    }
    cin >> B;
    for (int i = 0; i < B; i++) {
        cin >> U[i] >> V[i];
        U[i]--; V[i]--;
    }
    int ans = 0;
    for (int state = 0; state < 1<<B; state++) {
        ans = max(ans, calc(state));
    }
    cout << ans << endl;
    return 0;
}