求调,玄关
查看原帖
求调,玄关
878013
_Supernova楼主2024/8/6 12:07

94pts94pts 求调,玄关!

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair <int, int> pii;
const int N = 2e5 + 5;
int n, m;
vector <int> G[N];
int deg[N];
bool use[N];
set <pii> s;
vector <int> pg; // Point_Group
int cnt, ans = 1;
void EX_Topological_sorting(void) {
	for (int i = 1; i <= n; ++i) {
		s.insert(make_pair(deg[i], i));
	}
	while (s.size() && s.begin() -> first != (--s.end()) -> first) {
		int u = s.begin() -> second;
		s.erase(s.begin());
		use[u] = true;
		for (int v : G[u]) {
			if (use[v]) continue;
			s.erase(make_pair(deg[v], v));
			--deg[v];
			s.insert(make_pair(deg[v], v));
		}
	}
	for (auto x : s) {
		pg.emplace_back(x.second);
		//printf("%d ", x.second);
	}
	return ;
}
int main(void) {
	//freopen("clique.in", "r", stdin);
	//freopen("clique.out", "w", stdout);
	scanf("%d", &n);
	for (int u = 1, ki; u <= n; ++u) {
		scanf("%d", &ki);
		for (int j = 1, v; j <= ki; ++j) {
			scanf("%d", &v);
			G[u].push_back(v);
			++deg[v];
		}
	}
	EX_Topological_sorting(); // ex拓扑排序
	if (deg[pg[0]] + 1 != pg.size()) {
		printf("0");
		return 0;
	}
	for (int u = 1; u <= n; ++u) {
		for (int v : G[u]) {
			if (use[u] && use[v]) {
				printf("0");
				return 0;
			}
		}
	}
	for (int i = 1; i <= n; ++i) {
		deg[i] = G[i].size();
	}
	for (int u : pg) {
		bool flag = true;
		for (int v : G[u]) {
			if (use[v]) {
				flag = false;
				break;
			}
		}
		if (flag) {
			++ans;
			for (int v = 1; v <= n; ++v) {
				if (use[v] && v != u && deg[v] == pg.size() - 1) {
					++ans;
				}
			}
		}
	}
	printf("%d", ans);
	return 0;
}
2024/8/6 12:07
加载中...