洛谷 P3443 题解

题意

求一条以 $1$ 为起点的有向图欧拉回路，且欧拉回路序列中包含给出的 $t$ 个序列，注意每条边只能用一次。

思路

题中要求 $t$ 个序列都要包含，直接写不太好操作。因此考虑在给出 $t$ 个序列的首尾之间建边，并把序列中间经过的边删掉，从而防止重复走。比如说给出一个序列 $a \to b \to c \to d$，我们在 $a \to d$ 之间建一条边，然后把 $a \to b$，$b \to c$，$c \to d$ 这三条边删掉。

然后想一下什么情况下无解：

• 给出的序列中有不存在的边，即输入时没有 $u \to v$ 这条边，但给出的序列中有 $u \to v$ 这个序列。
• 同一条边用两次。
• 给出的点不能组成一个连通块。
• 给出的点不能形成欧拉回路，即有部分点的入度不等于出度。

第一种情况直接用数据结构标记输入的每条边，如果序列中出现未标记的边则无解。

第二种情况需要用双向链表记录每条边在给出序列中的前驱后继来判断。比如说一个序列 $a \to b \to c$，记 $a \to b$ 这条边为 $s$，$b \to c$ 这条边为 $d$，那么如果 $s$ 已经有了后继且后继不是 $d$，或者 $d$ 已经有了前驱且前驱不是 $s$，那么无解，为了判断出现环的情况，还需要用并查集维护一下。

注意第三种情况和第四种情况是在删边和添设新边后的图判断的，而不是初始的图。第三种情况 dfs 跑一遍，统计搜到的节点个数即可，不要忘了加上因为删边而不联通的点。第四种情况对于有向图有欧拉回路充要条件就是每个点入度等于出度。

之后跑一遍欧拉回路统计路径即可。

代码

#include<bits/stdc++.h>
#define ll long long 
using namespace std;
const ll N=5e5+10;
ll n,m,t,deg[N],p[N],a[N],b[N],cnt,f[N],d[N],top,st[N],in[N],fa[N];
vector<pair<ll,ll> >e[N],E[N];
unordered_map<ll,unordered_map<ll,ll> >vis;
unordered_map<ll,ll>mp;
vector<ll>vt[N],G[N];
ll get_hash(ll u,ll v){
	return 1ll*u*N+v;
}
ll find(ll x){
	if(fa[x]==x)return x;
	fa[x]=find(fa[x]);
	return fa[x];
}
void dfs(ll x){
	if(!f[x])f[x]=1,cnt++;
	for(ll &i=d[x];i<E[x].size();){
		pair<ll,ll>p=E[x][i++];
		dfs(p.first);
		if(p.second>m)st[++top]=p.second;
	}
	st[++top]=x;
}
int main(){
	scanf("%lld%lld",&n,&m);
	for(ll i=1;i<=m;i++){
		scanf("%lld%lld",&a[i],&b[i]);
		e[a[i]].push_back(make_pair(b[i],i));
		mp[get_hash(a[i],b[i])]=fa[i]=i;
	}
	scanf("%lld",&t);
	for(ll i=1;i<=t;i++){
		ll k;
		scanf("%lld",&k);
		for(ll j=1;j<=k;j++){
			scanf("%lld",&p[j]);
		} 
		for(ll j=1;j+1<k;j++){
			ll u=mp[get_hash(p[j],p[j+1])],v=mp[get_hash(p[j+1],p[j+2])];
			if(!u||!v){
				printf("NIE\n");
				return 0;
			}
			if(vis[u][v])continue;
			if(G[u].size()||deg[v]||find(u)==find(v)){
				printf("NIE\n");
				return 0;
			}
			vis[u][v]=1;G[u].push_back(v);deg[v]++;fa[fa[u]]=fa[v];
		}
	}
	ll id=m; 
	for(ll i=1;i<=m;i++){
		if(deg[i]||!G[i].size())continue;
		ll v=i;id++;
		while(1){
			if(!G[v].size())break;
			vt[id].push_back(b[v]);
			v=G[v][0];
		}
		E[a[i]].push_back(make_pair(b[v],id));
	}
	for(ll i=1;i<=n;i++){
		for(ll j=0;j<e[i].size();j++){
			pair<ll,ll>p=e[i][j];
			if(!deg[p.second]&&!G[p.second].size())E[i].push_back(p);
		}
	}
	for(ll i=1;i<=n;i++){
		for(ll j=0;j<E[i].size();j++){
			in[E[i][j].first]++;
		}
	}
	for(ll i=1;i<=n;i++){
		if(in[i]!=E[i].size()){
			printf("NIE\n");
			return 0;
		}
		else if(E[i].size()==0)cnt++;
	}
	dfs(1);
	if(cnt!=n){
		printf("NIE\n");
		return 0;
	}
	printf("TAK\n");
	while(top){
		if(st[top]>m)for(ll i=0;i<vt[st[top]].size();i++)printf("%lld\n",vt[st[top]][i]);
		else printf("%lld\n",st[top]);
		--top;
	}
	return 0;
}