KUPC2012 C : ソーシャル

問題概要

N(<100)匹のうさぎがいる。このうちいくつかのペアは仲が悪い。今うさぎをK個の集合に分けている。仲の悪いうさぎと同じ集合にいれられたうさぎの個数を求める問題。

解法

愚直に実装する。

acceptされたコード

#include <cstdio>
#include <algorithm>
using namespace std;

const int MAX_N = 50;

int N, K;
bool badPair[MAX_N][MAX_N];
bool feelBad[MAX_N];
int ls[MAX_N];
int ms[MAX_N][MAX_N];

void init() {
	scanf("%d%d", &N, &K);

	for (int i = 0; i < K; ++i) {
		scanf("%d", ls + i);
		for (int j = 0; j < ls[i]; ++j) {
			scanf("%d", ms[i]+j);
			--ms[i][j];
		}
	}
	int R;
	scanf("%d", &R);
	for (int i = 0; i < R; ++i) {
		int x, y;
		scanf("%d%d", &x, &y);
		--x; --y;
		badPair[x][y] = badPair[y][x] = true;
	}
}

int solve() {
	for (int i = 0; i < K; ++i) {
		for (int j = 0; j < ls[i]; ++j) {
			for (int k = j + 1; k < ls[i]; ++k) {
				if (badPair[ms[i][j]][ms[i][k]]) {
					feelBad[ms[i][j]] = feelBad[ms[i][k]] = true;
				}
			}
		}
	}

	return count(feelBad, feelBad + N, true);
}

int main() {
	init();
	printf("%d\n", solve());

	return 0;
}