玄关求条WA on 3# 23#
查看原帖
玄关求条WA on 3# 23#
340732
xinlin楼主2024/10/23 16:18
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
const int N = 5005;
bool g[N][N];
int rd[N], rk[N];
int jh[N], cnt = 0;
bool bjh[N];
bool cmp(int x, int y) {
	return rd[x] > rd[y];
}
bool check(int x) {
	for(int i = 1; i <= cnt; ++i) {
		if(g[jh[i]][x] == false) return false;
	}
	return true;
}
bool fk[N];
int ccf[N];
int main(){
	int n;
	scanf("%d", &n);
	int Maxrd = 0, p;
	for(int i = 1; i <= n; ++i) {
		int x, v;
		scanf("%d", &rd[i]);
		for(int j = 1; j <= rd[i]; ++j) {
			scanf("%d", &v);
			g[i][v] = true;
			g[v][i] = true;
		}
		rk[i] = i;
	}
	std::sort(rk + 1, rk + n + 1, cmp);
	for(int i = 1; i <= n; ++i) {
		if(check(rk[i])) jh[++cnt] = rk[i];
	}
	if(cnt == n || cnt == 1) {
		printf("%d", n);
		return 0;
	}
	for(int i = 1; i <= cnt; ++i) {
		bjh[jh[i]] = true;
	}
	for(int i = 1; i <= n; ++i) {
		if(bjh[i] == true) continue;
		for(int j = 1; j <= n; ++j) {
			if(g[i][j] == true && bjh[j] == false) {
				printf("0");
				return 0;
			}
		}
	}
//	for(int i = 1; i <= n; ++i) {
//		if(bjh[i] == true) continue;
//		if(rd[i] != cnt - 1) continue; 
//	}
	int ans = 1;
	for(int i = 1; i <= n; ++i) {
		if(bjh[i] == false) continue;
		bool f = true;
		for(int j = 1; j <= n; ++j) {
			if(g[i][j] == true && bjh[j] == false) {
				f = false;
				break;
			}
		}
		if(f == true) {
			fk[i] = true;
			++ans;
		}
	}
	
	for(int i = 1; i <= n; ++i) {
		if(bjh[i] == true) continue;
		if(rd[i] != cnt - 1) continue; 
		int p;
		for(int j = 1; j <= n; ++i) {
			if(g[i][jh[j]] == true) {
				p = j;
				break;
			}
		}
		if(fk[p] == true) ++ccf[p];
	}
	for(int i = 1; i <= n; ++i) {
		if(ccf[i] > 1) ans += ccf[i] - 1;
	}
	printf("%d", ans);
	return 0;
}
/*
5
2 2 3
2 1 3
4 1 2 4 5
2 1 3
1 3
*/
2024/10/23 16:18
加载中...