天下一プログラマーコンテスト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;
}