天下一プログラマーコンテスト2012 予選A C : 敵対的引用
問題概要
頂点数N(<10^5)、辺集合E(|E|<10^4)の有向グラフが与えられる。今、辺の列(<150)に関する一部の情報(それぞれの辺が辺集合Eに含まれるかどうか)が与えられるので、該当するパスの終点となりうる頂点の個数を求める問題。
解法
BFSするだけ。ただしEの補集合を陽に持つことはできないので、その部分だけ気をつける。
acceptされたコード
#include <cstdio> #include <cstring> #include <cctype> #include <vector> #include <algorithm> using namespace std; const int MAX_L = 300; const int MAX_N = (int)(1e5); const int MAX_M = (int)(1e4); int N, M, G; char buf[MAX_L + 2]; vector<int> hates[MAX_N]; bool cands[MAX_N], nextCands[MAX_N]; void init() { scanf("%d%d", &N, &M); for (int i = 0; i < M; ++i) { int x, y; scanf("%d%d", &x, &y); --x; --y; hates[x].push_back(y); } scanf(" %s ", buf); } void updateHate() { memset(nextCands, false, sizeof(nextCands)); for (int i = 0; i < N; ++i) { for (int j = 0; j < (int)hates[i].size(); ++j) { nextCands[i] |= cands[hates[i][j]]; } } memcpy(cands, nextCands, sizeof(cands)); } void updateLike() { int numCands = count(cands, cands + N, true); for (int i = 0; i < N; ++i) { int count = 0; for (int j = 0; j < (int)hates[i].size(); ++j) { if (cands[hates[i][j]]) { ++count; } } nextCands[i] = count != numCands; } memcpy(cands, nextCands, sizeof(cands)); } int solve() { int p = 0; const int L = strlen(buf); for (; p < L; ++p) { if (isdigit(buf[p])) { G = G * 10 + (buf[p] & 15); } else if (G) { break; } } --G; cands[G] = true; bool isHated = buf[p] == 'w'; if (isHated) { ++p; } isHated ? updateHate() : updateLike(); for (;;) { if (p == L) { break; } ++p; isHated = buf[p] == 'w'; if (isHated) { ++p; ++p; } isHated ? updateHate() : updateLike(); } return count(cands, cands + N, true); } int main() { init(); printf("%d\n", solve()); return 0; }