年功序列

题目描述

在虚拟国度里多了不少 Virtual oier，为了树立对后辈的威信，从第 $1$ 个 Virtual oier 开始的 oier 们搞起了年功序列的制度。
虚拟国度的创始人 oier Chtholly 感受很是有趣，因而他决定观测 $1$ 到 $n$ 这些人，他观测到了一些有趣的现象：虚拟国度里有一些凳子，若是 $a$ 是 的先辈则 能在 前面获得凳子
Chtholly的观测能够构成 $m$ 个序列，每一个序列有 $k$ 个元素 $a_{1}, a_{2}, a_{3}, ······, a_{k}$。表示在 $a_{i}$ 有凳子前 $a_{1}, a_{2}, a_{3}, ······, a_{i - 1}$ 必须有凳子。( $a_{i - 1}$ 是 $a_{i}$ 的前辈)
例如 k = 3 时： $a = 1，2，3$，表示 $3$ 有凳子前 $1, 2$必须都有凳子， $2$ 有凳子前 $1$ 必须有凳子。
但 Chtholly 年纪大了记忆力未必好，若是第 $i$ 个序列与前 $i - 1$ 个序列冲突的话那么就只须要考虑前 $i - 1$ 个序列就行了。(忽略第 $i$ 个序列)
Chtholly 但愿知道 $1$ 到 $n$ 我的的年功序列的最小字典序。html

输入格式

第一行两个数 $n, m$
接下来 m 行每行第一个数为 $k$，接下来 $k$ 个数为此次观测构成的序列node

输出格式

输出 $n$ 个数构成的最小字典序。web

样例

样例输入

4 3
3 1 2 3
2 4 2
3 3 4 1app

样例输出

1 4 2 3svg

样例解释

第三个观测序列与前两个观测序列冲突不考虑，前两个观测序列能够构成 $1$ $4$ $2$ $3$ 或者 $4$ $1$ $2$ $3$ 这两个序列，字典序小的为 $1$ $4$ $2$ $3$。spa

数据范围与提示

$30$%的数据， $n \leq 10, m \leq 4$
$50$%的数据， $n \leq 10000, m \leq 5000$
$100$%的数据， $n \leq 100000, m \leq 50000, k \leq n$code

分析

这道题看似很难、很复杂，实际上是道简单的拓扑排序。
咱们能够把 $a[1]$ ~ $a[i - 1]$ 当作 $a[i]$ 的入度。(下面也这样说明)
可是咱们只须要把 $a[i - 1]$ 当作 $a[i]$ 的入度便可。 $($ 由于咱们求到 $a[i - 1]$ 的时候，前面的 $a[1]$ ~ $a[i - 2]$ 必定是求过的 $($ 否则不会求到 $a[i - 1]$ 的 $)$ $)$
——可是这道题的难点在于冲突的状况orm

思路

咱们先输入第 $i$ 组的数据 ，把 这组数据 及 之前的数据(没有舍弃的数据) 进行拓扑排序，再判断是否出现了环：xml

• 若是出现了，就把 这组数据舍弃 (同时也要把 新加进来的 入度 和 每一个点的入度个数 还原)。

代码

正解代码以下：htm

#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
using namespace std;

const int MAXN = 1e5 + 5;
int N, M, K;
int num[MAXN];
vector<int> ans, E[MAXN];
int in[MAXN]; // 每一个人的前辈个数 
bool vis[MAXN];
struct node
{
	int numn;
	node(){}
	node (int n) { numn = n; }
	friend bool operator < (node a, node b) { return a.numn > b.numn; } // 字典序排序 
};

void toposort() // 拓扑排序 
{
	priority_queue<node> q;
	for (int i = 1; i <= N; i++)
		if (in[i] == 0) q.push(node(i)); // 不必定每一个人都有前辈, 因此不须要判断每一个人是否被输入 
	while (!q.empty())
	{
		int u = q.top().numn; q.pop();
		ans.push_back(u);
		int siz = E[u].size();
		for (int i = 0; i < siz; i++)
		{
			int v = E[u][i];
			--in[v];
			if (in[v] == 0) q.push(node(v));
		}
	}
}

bool check(int u) // 判断是否产生环 
{
	int siz = E[u].size();
	for (int i = 0; i < siz; i++)
	{
		int v = E[u][i];
		if (vis[v]) return 0;
		vis[v] = 1;
		if (!check(v)) return 0;
	}
	vis[u] = 0;
	return 1;
}

int main()
{
	scanf("%d %d", &N, &M);
	for (int i = 1; i <= M; i++)
	{
		scanf("%d", &K);
		for (int j = 1; j <= K; j++)
		{
			scanf("%d", &num[j]);
			if (j == 1) continue; // 第1我的没有前辈 
			E[num[j - 1]].push_back(num[j]), ++in[num[j]];
		}
		memset(vis, 0, sizeof(vis));
		vis[num[1]] = 1;
		if (!check(num[1])) // 为何从第1人开始判断, 就留给读者本身思考了 
		{
			// 还原 
			for (int j = 2; j <= K; j++)
			{
				 // 删除这个入度 
				--in[num[j]];
				E[num[j - 1]].pop_back();
			}
			break;
		}
	}
	toposort();
	int siz = ans.size();
	for (int i = 0; i < siz; i++)
		printf("%d ", ans[i]);
	return 0;
}