# 題目: UVa 11659 - Informants

# 題目說明

題目給n個線人，並給a條規則，求最大可信賴的線人數

---

INPUT:
每筆測資先輸入兩個整數n、a，n代表線人數、a代表規則數
接下來有a行，每行輸入兩個整數x、y

• 若y > 0，代表線人x信賴線人y
• 若y < 0，代表線人x不信賴線人y

---

OUTPUT:
輸出最大可信賴的線人數

# 解題方法

使用correct與wrong分別儲存信賴與不信賴，儲存分法為2進位

遍歷所有可能的線人組合

分別判斷各個線人是否存在這次的線人組合中

若存在則進一步判斷規則是否有矛盾

當此組合中的線人全部判斷完，且規則都沒有矛盾，則可計算這次可信賴的線人數

# 參考程式碼

#include <iostream>
#include <vector>

using namespace std;

static auto fast_io = []
{
	ios::sync_with_stdio(false);
	cout.tie(nullptr);
	cin.tie(nullptr);
	return 0;
}();

int main()
{
	int n, a, x, y;

	while (cin >> n >> a, n + a)
	{
		// init
		vector<int> correct(n + 1, 0);
		vector<int> wrong(n + 1, 0);
		int max_num = (1 << n);
		int ret = 0;

		// input
		for (int i = 0; i < a; ++i)
		{
			cin >> x >> y;
			if (y > 0) correct[x] |= (1 << (y - 1));  // if 1 trust 3 and 4, correct[1] = 1100
			else wrong[x] |= (1 << (-y - 1));
		}

		for (int i = 0; i < max_num; ++i) // all possible combination
		{
			bool feasible = true;

			for (int j = 1; j <= n; ++j) // each person 
			{
				int p = 1 << (j - 1);
				if ((i & p) == 0) continue; // j doesn't exist in i
				if ((i & wrong[j]) != 0 || (i & correct[j]) != correct[j]) // is there a contradiction
				{
					feasible = false;
					break;
				}
			}

			if (feasible)
			{
				int cnt = 0, cpy = i;
				while (cpy) cnt += cpy & 1, cpy >>= 1; // count the number of '1' in i (bitwise)
				ret = max(ret, cnt);
			}
		}

		cout << ret << "\n";
	}
}

# 參考資料

https://theriseofdavid.github.io/2021/04/23/UVa/UVa11659/