年功序列

题目描述

在虚拟国度里多了很多 Virtual oier，为了树立对后辈的威信，从第 1 1 1 个 Virtual oier 开始的 oier 们搞起了年功序列的制度。
虚拟国度的创始人 oier Chtholly 感觉非常有趣，于是他决定观测 1 1 1 到 n n n 这些人，他观测到了一些有趣的现象：虚拟国度里有一些凳子，如果 a a a 是 的先辈则 能在 前面得到凳子
Chtholly的观测可以构成 m m m 个序列，每个序列有 k k k 个元素 a 1 , a 2 , a 3 , ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ , a k a_{1}, a_{2}, a_{3}, ······, a_{k} a1​,a2​,a3​,⋅⋅⋅⋅⋅⋅,ak​。表示在 a i a_{i} ai​ 有凳子前 a 1 , a 2 , a 3 , ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ , a i − 1 a_{1}, a_{2}, a_{3}, ······, a_{i - 1} a1​,a2​,a3​,⋅⋅⋅⋅⋅⋅,ai−1​ 必须有凳子。( a i − 1 a_{i - 1} ai−1​ 是 a i a_{i} ai​ 的前辈)
例如 k = 3 时： a = 1 ， 2 ， 3 a = 1，2，3 a=1，2，3，表示 3 3 3 有凳子前 1 , 2 1, 2 1,2必须都有凳子， 2 2 2 有凳子前 1 1 1 必须有凳子。
但 Chtholly 年纪大了记忆力未必好，如果第 i i i 个序列与前 i − 1 i - 1 i−1 个序列冲突的话那么就只需要考虑前 i − 1 i - 1 i−1 个序列就好了。(忽略第 i i i 个序列)
Chtholly 希望知道 1 1 1 到 n n n 个人的年功序列的最小字典序。

输入格式

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

输出格式

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

样例

样例输入

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

样例输出

1 4 2 3

样例解释

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

数据范围与提示

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

分析

这道题看似很难、很复杂，其实是道简单的拓扑排序。
我们可以把 a [ 1 ] a[1] a[1] ~ a [ i − 1 ] a[i - 1] a[i−1] 看成 a [ i ] a[i] a[i] 的入度。(下面也这样说明)
但是我们只需要把 a [ i − 1 ] a[i - 1] a[i−1] 看成 a [ i ] a[i] a[i] 的入度即可。 ( ( ( 因为我们求到 a [ i − 1 ] a[i - 1] a[i−1] 的时候，前面的 a [ 1 ] a[1] a[1] ~ a [ i − 2 ] a[i - 2] a[i−2] 一定是求过的 ( ( ( 不然不会求到 a [ i − 1 ] a[i - 1] a[i−1] 的 ) ) ) ) ) )
——但是这道题的难点在于冲突的情况

思路

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

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

代码

正解代码如下：

#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;
}