P3443 [POI2006] LIS-The Postman

代码见下

#include<utility>
#include<map>
#include<cstdio> 
#include<iostream>
using namespace std;
const int maxn=5e5+5;
#define F first
#define S second
int n,m,t,cnt;
struct edg{
	int nt,to;
}eg[maxn<<1];
int s[maxn];
bool f[maxn];
pair<int,int>e[maxn];
int w[maxn],head[maxn],in[maxn];
int pre[maxn],nxt[maxn],b[maxn];
inline void add_e(int u,int v,int id){
	eg[++cnt].to=v;
	eg[cnt].nt=head[u];
	head[u]=cnt;
	w[cnt]=id;
	in[u]++,in[v]--;
}
map<int,int>h[maxn];
inline void no(){
	cout<<"NIE";
	exit(0);
} 
inline void prepare(){
	for(int i=1;i<=n;i++)
		s[i]=i;
}
int finds(int u){
	if(u!=s[u]) s[u]=finds(s[u]);
	return s[u];
}
inline void union_point(int u,int v){
	u=finds(u);
	v=finds(v);
	if(u!=v) s[v]=s[u];
}
int vis[maxn],stk[maxn],top;
inline void dfs(int u,int fa){
	for(int &i=head[u];i;i=eg[i].nt){
		int y=eg[i].to;
		if(vis[y]) continue;
		vis[y]=1;
		dfs(y,i);
	}
	stk[++top]=fa;
}
int main(){
	cin>>n>>m;
	prepare();
	for(int i=1;i<=m;i++){
		int u,v;
		cin>>u>>v;
		e[i]=make_pair(u,v);
		union_point(u,v);
		in[v]++,in[u]--;
		f[u]=1,f[v]=1;
		h[u][v]=i;
	}
	for(int i=1;i<=n;i++){
		if(in[i])
			no();
	}
	int o=0;
	for(int i=1;i<=n;i++){
		if(s[i]==i&&f[i]) o++;
		if(o==2) no();
	}
	cin>>t;
	for(int i=1;i<=t;i++){
		int k,last;
		cin>>k>>last;
		for(int j=1;j<k;j++){
			int x;
			cin>>x;
			if(h[last].find(x)==h[last].end())
				no();
			b[j]=h[last][x];
			last=x;
		}
		for(int j=2;j<k;j++){
			if(!pre[b[j]])
				pre[b[j]]=b[j-1];
			else if(pre[b[j]]!=b[j-1])
				no();
			if(!nxt[b[j-1]])
				nxt[b[j-1]]=b[j];
			else if(nxt[b[j-1]]!=b[j])
				no();
		}
	}
	int tot=0;
	for(int i=1;i<=m;i++){
		if(!pre[i]){
			tot++;
			int j,t;
			for(j=i;j;j=nxt[j]){
				t=j;
				tot++;
			}
			add_e(e[i].F,e[t].S,i);
		}
	}
	if(tot<m) no();
	for(int i=1;i<=n;i++){
		if(in[i]) no();
	}
	cout<<"TAK"<<endl;
	dfs(1,0);
	top--;
	cout<<e[w[stk[top]]].F<<endl;
	for(int i=top;i>=1;i--){
		int j=w[stk[i]];
		while(j){
			printf("%d\n",e[j].S); 
			j=nxt[j];
		}
	}
	cout<<"1";
	return 0;
}