年功序列 题解

年功序列

分析

此题如果没有Chtholly年纪大了记忆力未必好，如果第\(i\)个序列与前\(i−1\)个序列冲突的话那么就只需要考虑前\(i−1\)个序列就好了的限制，就会是一道\(topsort\)的板题。

判断是否有环

建立邻接表

输入时前后相连，建立邻接表，如果无环则会形成一个长链。

判环

从\(x[1]\)开始判断，如果有环，就直接退出循环。

具体方法

bool check(int x) {
	for (int i = 0; i < G[x].size(); i++) {
		if (vis[G[x][i]] == 1) {//如果已经访问过，就说明有环存在
			return 0;
		}
		vis[G[x][i]] = 1;
		if (check(G[x][i]) == 0) {
			vis[G[x][i]] = 0;//重置
			return 0;
		}
	}
	vis[x] = 0;//重置
	return 1;
}

实现

#include <cstring>
#include <queue>
#include <vector>
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
const int MAXN = 1e5 + 5;

int n, m, x[MAXN], deg[MAXN], ans[MAXN], cnt;
bool vis[MAXN];

vector<int> G[MAXN];
priority_queue<int, vector<int>, greater<int> > q;

bool check(int x) {
	for (int i = 0; i < G[x].size(); i++) {
		if (vis[G[x][i]] == 1) {
			return 0;
		}
		vis[G[x][i]] = 1;
		if (check(G[x][i]) == 0) {
			vis[G[x][i]] = 0;
			return 0;
		}
	}
	vis[x] = 0;
	return 1;
}

void topsort() {
	for (int i = 1; i <= n; i++) {
		if (deg[i] == 0) {
			q.push(i);
		}
	}
	while (q.size()) {
		int u = q.top();
		q.pop();
		ans[++cnt] = u;
		for (int i = 0; i < G[u].size(); i++) {
			deg[G[u][i]] --;
			if (deg[G[u][i]] == 0) {
				q.push(G[u][i]);
			}
		}
	}
	for (int i = 1; i <= n; i++) {
		printf ("%d ", ans[i]);
	}
}

int main() {
	scanf ("%d %d", &n, &m);
	while (m --) {
		int k;
		scanf ("%d", &k);
		memset(vis, 0, sizeof(vis));
		for (int i = 1; i <= k; i++) {
			scanf ("%d", &x[i]);
			if (i != 1) {
				deg[x[i]] ++;
				G[x[i - 1]].push_back(x[i]);
			}
		}
		vis[x[1]] = 1;
		if (! check(x[1])) {
			for (int i = 2; i <= k; i++) {
				G[x[i - 1]].pop_back();
				deg[x[i]] --;
			}
			break;
		}
	}
	topsort();
	return 0;
}