UVA 11748 - Rigging Elections（dfs)

UVA 11748 - Rigging Elections

題目鏈接

題意：n個人選舉，給出m個人的投票人對於每個人的優先級，現在你想讓第c個人贏，問能不能

思路：對於兩個人上場，如果a能贏b,就建一條a->b的邊，然後問題其實就變成能否以c為根節點是一棵樹，直接dfs一遍即可

代碼：

#include 
#include 
#include 
using namespace std;

const int N = 105;

int n, m, c, a[N][N], vis[N];
vector g[N];

int dfs(int u) {
	vis[u] = 1;
	int ans = 1;
	for (int i = 0; i < g[u].size(); i++) if (!vis[g[u][i]])
		ans += dfs(g[u][i]);
	return ans;
}

int main() {
	while (~scanf("%d%d%d", &n, &m, &c) && n) {
		int u;
		for (int i = 1; i <= n; i++)
			g[i].clear();
		for (int i = 1; i <= m; i++)
			for (int j = 1; j <= n; j++) {
				scanf("%d", &u);
				a[i][u] = j;
			}
		for (int i = 1; i <= n; i++) {
			for (int j = i + 1; j <= n; j++) {
				int cnt = 0;
				for (int k = 1; k <= m; k++) {
					if (a[k][i] < a[k][j])
						cnt++;
					if (cnt > m / 2) break;
				}
				if (cnt > m / 2) g[i].push_back(j);
				else g[j].push_back(i);
			}
		}
		memset(vis, 0, sizeof(vis));
		printf("%s\n", dfs(c) == n ? "yes" : "no");
	}
	return 0;
}