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; }