提出 #74758092

---

ソースコード 拡げる

#include<cstdio>
int n, m, k;
int edge[200100][2];
int em[2010][2010];
int uft[2010];
int ecnt[2010];
int dp[2010][2];
int uftf(int x) {
	if (x == uft[x])return x;
	int res = uftf(uft[x]);
	uft[x] = res;
	return res;
}
int main() {
	int tcn;
	scanf("%d", &tcn);
	while (tcn--) {
		scanf("%d%d%d", &n, &m, &k);
		for (int i = 0; i < m; i++) {
			scanf("%d%d", &edge[i][0], &edge[i][1]);
		}
		if (k % 2 == 0 || n >= 2000 || n * n >= 8 * m) {
			printf("Yes\n");
			continue;
		}
		for (int i = 0; i <= n; i++) {
			uft[i] = i;
			dp[i][0] = 0;
			dp[i][1] = 0;
			for (int j = 0; j <= n; j++) {
				em[i][j] = 0;
			}
		}
		for (int i = 0; i < m; i++) {
			em[edge[i][0] - 1][edge[i][1] - 1] = 1;
			em[edge[i][1] - 1][edge[i][0] - 1] = 2;
		}
		for (int i = 0; i < n; i++) {
			ecnt[i] = 0;
			for (int j = 0; j < n; j++) {
				if (em[i][j] == 1) {
					ecnt[i]++;
				}
				else if (em[i][j] == 0 && j < i) {
					ecnt[i]++;
				}
			}
			ecnt[i] %= 2;
			for (int j = 0; j < n; j++) {
				if (em[i][j] == 0) {
					int pi = uftf(i);
					int pj = uftf(j);
					if (pi != pj) {
						uft[pi] = uft[pj];
					}
				}
			}
		}
		for (int i = 0; i < n; i++) {
			dp[uftf(i)][ecnt[i] % 2]++;
		}
		int desteven = (n + 1) / 2;
		int mineven = 0;
		int maxeven = 0;
		for (int i = 0; i < n; i++) {
			int ceven = dp[i][0];
			int codd = dp[i][1];
			mineven += ceven % 2;
			maxeven += ceven + codd - (codd % 2);
		}
		if (mineven <= desteven && desteven <= maxeven) {
			printf("Yes\n");
		}
		else {
			printf("No\n");
		}
	}
	return 0;
}

提出情報

ジャッジ結果