[Codeforces] 731D. 80-th Level Archeology

題目連結:http://codeforces.com/problemset/problem/731/D

---

我覺得我的作法感覺不太對(?但還是講一下好了
我的做法是先把大小關係建成一張DAG，而這樣的話會發現題目變成說可不可以找到一種拓樸排序方法使得序列會是循環的字串，而又已經知道循環其實就只有可能中間斷開一個而已，所以我們不妨找到中間斷開的那個關係，並追本朔源到最前面的那個，從他開始拓樸排序，看會不會是好的。

#include <bits/stdc++.h>
using namespace std;
#define PB push_back
#define FF first
#define SS second
const int N = 500000 + 5;
const int C = 1000000 + 5;

class DJS{
	private:
		vector<int> arr;
	public:
		inline void init(int n){
			arr.resize(n);
			for(int i=0;i<n;i++) arr[i]=i;
		}
		int query(int x){
			if(arr[x]!=x) arr[x] = query(arr[x]);
			return arr[x];
		}
		void merge(int a, int b){
			int u = query(a), v = query(b);
			arr[max(u, v)]=min(u, v);
		}
} djs;

vector<int> G[C], cur;
int in[C];

inline void kill(){cout<<"-1\n";exit(0);}

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	int n, c; cin>>n>>c;
	djs.init(c+1);
	int sz; cin>>sz;
	for(int j=0;j<sz;j++){
		int x; cin>>x;
		cur.PB(x);
	}
	int ll = c+1;
	for(int i=1;i<n;i++){
		bool flag = 1;
		cin>>sz;
		vector<int> tmp;
		for(int j=0;j<sz;j++){
			int x; cin>>x;
			tmp.PB(x);
			if(j >= (int)cur.size()) flag = 0;
			if(!flag) continue;
			if(tmp[j] != cur[j]){
				flag = 0;
				if(tmp[j] < cur[j]) ll = cur[j];
				else djs.merge(cur[j], tmp[j]);
				G[cur[j]].PB(tmp[j]);
				in[tmp[j]]++;
			}
		}
		if(flag and sz<(int)cur.size()) kill();
		cur = tmp;
	}
	if(ll==c+1) ll = 1;
	ll=djs.query(ll);
	for(int i=ll;i<=c;i++){
		if(in[i]!=0) kill();
		for(auto u: G[i]){
			if(in[u]==0) continue;
			in[u]--;
		}
	}
	for(int i=1;i<ll;i++){
		if(in[i]!=0) kill();
		for(auto u: G[i]){
			if(in[u]==0) continue;
			in[u]--;
		}
	}
	cout<<(1-ll+c)%c<<'\n';
	return 0;
}