SPOJ 11576 TRIP2 - A Famous King’s Trip 【Tarjan+欧拉回路】

自我吐槽

（哭

题目传送门

SPOJ
洛谷

题目大意

让你在简单无向图上删去2条边，使该图联通并存在欧拉回路
输出字典序最小的一对边

思路

考虑到存在欧拉回路的充要条件，即
$$i{n}_x\equiv 0(\mathrm{mod}2)\forall i(1\le i\le n)$$
于是考虑根据奇点个数进行计算

1.奇点有 $4$ 个

直接两两配对即可，最多 $3$ 种情况，枚举即可

2.奇点有 $2$ 个

需要找到一个中间点进行配对，情况数较多，需要tarjan去算边双和点双去进行判断
tip:此题有生成树做法，更简单，但我不会

3.其他情况

输出NO

对于第 $2$ 种情况，需要判断奇点是否为割点，中间点是否为割点，两奇点是否在同一个点双联通分量等

因而共计逾 $10$ 种状态，细节量与码量还是非常感人的

tip

细节点
正确写法

!((u==au&&v==av)
||(u==bu&&v==bv)
||(u==av&&v==au)
||(u==bv&&v==bu))

错误写法

((u==au&&v!=av)
||(u==bu&&v!=bv)
||(u==av&&v!=au)
||(u==bv&&v!=bu)
||(u!=au&&u!=bu&&u!=av&&u!=bv))

两者是存在区别的，感兴趣者可以自行枚举尝试

另：建议不要写这种写法，码量与细节点太多，配合上多测……

综上，在历时10小时11分钟27秒，我调过了这道题

Code

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+7;
int n,m,u[N],v[N],in[N],k,vis[N],in2[N],at[N],in3[N];
vector<int>vt,e[N];
vector<int>vtt,ds[N];
set<int>stt;
map<int,int>mp2[N],mp3[N],mp4[N];
void memeset(int x[N],int y,int p){for(int i=1;i<=n;i++)x[i]=y;
}
void dfs1(int u,int au,int av,int bu,int bv){vis[u]=1;for(int v:e[u])if(!vis[v]&&!((u==au&&v==av)||(u==bu&&v==bv)||(u==av&&v==au)||(u==bv&&v==bu)))dfs1(v,au,av,bu,bv);
}
bool easyck(int au,int av,int bu,int bv){memeset(vis,0,sizeof vis);dfs1(1,au,av,bu,bv);for(int i=1;i<=n;i++)if(!vis[i])return 0;return 1;
}
int low[N],dfn[N],idx,st,cut[N],cnt;
pair<int,int>stk[N<<1];
void tarjan(int u,int fa){dfn[u]=low[u]=++idx;int son=0;for(int v:e[u]){if(v==fa)continue;if(!dfn[v]){stk[++st]={u,v};tarjan(v,u);son++;if(low[v]<low[u])low[u]=low[v];if(low[v]>=dfn[u]){cnt++;pair<int,int>xx;cut[u]=1;stt.clear();ds[cnt].clear();mp4[cnt].clear();do{xx=stk[st--];stt.insert(xx.first);stt.insert(xx.second);mp4[cnt][xx.first]=mp4[cnt][xx.second]=1;at[xx.first]=at[xx.second]=cnt;}while(xx.first!=u&&xx.second!=v);for(auto i=stt.begin();i!=stt.end();i++)ds[cnt].push_back(*i);}if(low[v]>dfn[u])mp3[u][v]=mp3[v][u]=1;}else if(dfn[v]<low[u])low[u]=dfn[v];}if(u==1&&son==1)cut[u]=0;
}
bool quick(int u,int v){vtt.clear();for(int i=1;i<=cnt;i++)if(mp4[i].find(u)!=mp4[i].end()&&mp4[i].find(v)!=mp4[i].end()){vtt=ds[i];return 0;}return 1;
}
bool check(){if(m<=3)return 0;if(!easyck(0,0,0,0))return 0;for(int i=1;i<=n;i++)if(in[i]==1)return 0;vt.clear();for(int i=1;i<=n;i++)if(in[i]&1)vt.push_back(i);if(vt.size()==2){memeset(dfn,0,sizeof dfn);memeset(low,0,sizeof low);memeset(at,0,sizeof at);memeset(cut,0,sizeof cut);cnt=idx=st=0;tarjan(1,0);for(int i=1;i<=n;i++)mp3[i].clear();if(cut[vt[1]])swap(vt[1],vt[0]);if(cut[vt[0]]&&cut[vt[1]]){if(quick(vt[0],vt[1])){for(int i=1;i<=n;i++)if(in[i]>2&&in[i]%2==0&&mp2[i].find(vt[0])!=mp2[i].end()&&mp2[i].find(vt[1])!=mp2[i].end()&&easyck(u[mp2[i][vt[1]]],v[mp2[i][vt[1]]],u[mp2[i][vt[0]]],v[mp2[i][vt[0]]]))return 1;return 0;}else{memeset(in2,0,sizeof in2);for(int i:vtt)for(int v:e[i])if(cut[v])in2[v]++;if(in2[vt[0]]<2||in2[vt[1]]<2)return 0;for(int i=1;i<=n;i++)if(in[i]>2&&in[i]%2==0&&mp2[i].find(vt[0])!=mp2[i].end()&&mp2[i].find(vt[1])!=mp2[i].end()&&mp3[i].find(vt[0])==mp3[i].end()&&mp3[i].find(vt[1])==mp3[i].end())if(in2[i]>2||!cut[i])return 1;return 0;}}else if(cut[vt[0]]){if(quick(vt[0],vt[1])){for(int i=1;i<=n;i++)if(in[i]>2&&in[i]%2==0&&mp2[i].find(vt[0])!=mp2[i].end()&&mp2[i].find(vt[1])!=mp2[i].end()&&easyck(u[mp2[i][vt[1]]],v[mp2[i][vt[1]]],u[mp2[i][vt[0]]],v[mp2[i][vt[0]]]))return 1;return 0;}else{memeset(in2,0,sizeof in2);for(int i:vtt)for(int v:e[i])if(cut[v])in2[v]++;if(in2[vt[0]]<2)return 0;for(int i=1;i<=n;i++)if(in[i]>2&&in[i]%2==0&&mp2[i].find(vt[0])!=mp2[i].end()&&mp2[i].find(vt[1])!=mp2[i].end()&&mp3[i].find(vt[0])==mp3[i].end()&&mp3[i].find(vt[1])==mp3[i].end())if(in2[i]>2||!cut[i])return 1;return 0;}}else{if(at[vt[0]]!=at[vt[1]]){for(int i=1;i<=n;i++)if(in[i]>2&&in[i]%2==0&&mp2[i].find(vt[0])!=mp2[i].end()&&mp2[i].find(vt[1])!=mp2[i].end()&&easyck(u[mp2[i][vt[1]]],v[mp2[i][vt[1]]],u[mp2[i][vt[0]]],v[mp2[i][vt[0]]]))return 1;}else{quick(vt[0],vt[1]);memeset(in2,0,sizeof in2);for(int i:vtt)for(int v:e[i])if(cut[v])in2[v]++;for(int i=1;i<=n;i++)if(in[i]>2&&in[i]%2==0&&mp2[i].find(vt[0])!=mp2[i].end()&&mp2[i].find(vt[1])!=mp2[i].end())if(!cut[i]||in2[i]>2)return 1;}}return 0;}if(vt.size()==4){if(mp2[vt[0]].find(vt[1])!=mp2[vt[0]].end()&&mp2[vt[2]].find(vt[3])!=mp2[vt[2]].end()&&easyck(u[mp2[vt[0]][vt[1]]],v[mp2[vt[0]][vt[1]]],u[mp2[vt[2]][vt[3]]],v[mp2[vt[2]][vt[3]]]))return 1;if(mp2[vt[0]].find(vt[2])!=mp2[vt[0]].end()&&mp2[vt[1]].find(vt[3])!=mp2[vt[1]].end()&&easyck(u[mp2[vt[0]][vt[2]]],v[mp2[vt[0]][vt[2]]],u[mp2[vt[1]][vt[3]]],v[mp2[vt[1]][vt[3]]]))return 1;if(mp2[vt[0]].find(vt[3])!=mp2[vt[0]].end()&&mp2[vt[2]].find(vt[1])!=mp2[vt[2]].end()&&easyck(u[mp2[vt[0]][vt[3]]],v[mp2[vt[0]][vt[3]]],u[mp2[vt[2]][vt[1]]],v[mp2[vt[2]][vt[1]]]))return 1;return 0;}return 0;
}
pair<int,int>pii[N];
pair<int,int>p[4];
int tot;
main(){while(~scanf("%lld%lld",&n,&m)){for(int i=1;i<=n;i++)in[i]=0,mp2[i].clear(),e[i].clear();for(int i=1;i<=m;i++){scanf("%lld%lld",u+i,v+i),in[u[i]]++,in[v[i]]++,e[u[i]].push_back(v[i]);e[v[i]].push_back(u[i]);mp2[u[i]][v[i]]=mp2[v[i]][u[i]]=i;}bool flg=check();printf("Case %lld: ",++k);puts(flg?"YES":"NO");if(flg){if(vt.size()==4){p[1]=p[2]=p[3]={1e9,1e9};if(mp2[vt[0]].find(vt[1])!=mp2[vt[0]].end()&&mp2[vt[2]].find(vt[3])!=mp2[vt[2]].end()&&easyck(u[mp2[vt[0]][vt[1]]],v[mp2[vt[0]][vt[1]]],u[mp2[vt[2]][vt[3]]],v[mp2[vt[2]][vt[3]]])){p[1]={mp2[vt[0]][vt[1]],mp2[vt[2]][vt[3]]};if(p[1].first>p[1].second)swap(p[1].first,p[1].second);}if(mp2[vt[0]].find(vt[2])!=mp2[vt[0]].end()&&mp2[vt[1]].find(vt[3])!=mp2[vt[1]].end()&&easyck(u[mp2[vt[0]][vt[2]]],v[mp2[vt[0]][vt[2]]],u[mp2[vt[1]][vt[3]]],v[mp2[vt[1]][vt[3]]])){p[2]={mp2[vt[0]][vt[2]],mp2[vt[1]][vt[3]]};if(p[2].first>p[2].second)swap(p[2].first,p[2].second);}if(mp2[vt[0]].find(vt[3])!=mp2[vt[0]].end()&&mp2[vt[2]].find(vt[1])!=mp2[vt[2]].end()&&easyck(u[mp2[vt[0]][vt[3]]],v[mp2[vt[0]][vt[3]]],u[mp2[vt[2]][vt[1]]],v[mp2[vt[2]][vt[1]]])){p[3]={mp2[vt[0]][vt[3]],mp2[vt[2]][vt[1]]};if(p[3].first>p[3].second)swap(p[3].first,p[3].second);}sort(p+1,p+4);printf("%lld %lld",p[1].first,p[1].second);}if(vt.size()==2){tot=0;if(cut[vt[0]]&&cut[vt[1]]){if(quick(vt[0],vt[1])){for(int i=1;i<=n;i++)if(in[i]>2&&in[i]%2==0&&	mp2[i].find(vt[0])!=mp2[i].end()&&mp2[i].find(vt[1])!=mp2[i].end()&&easyck(u[mp2[i][vt[1]]],v[mp2[i][vt[1]]],u[mp2[i][vt[0]]],v[mp2[i][vt[0]]])){pii[++tot]={mp2[i][vt[0]],mp2[i][vt[1]]};if(pii[tot].first>pii[tot].second)swap(pii[tot].first,pii[tot].second);}}else{memeset(in2,0,sizeof in2);for(int i:vtt)for(int v:e[i])if(cut[v])in2[v]++;for(int i=1;i<=n;i++)if(in[i]>2&&in[i]%2==0&&mp2[i].find(vt[0])!=mp2[i].end()&&mp2[i].find(vt[1])!=mp2[i].end()&&mp3[i].find(vt[0])==mp3[i].end()&&mp3[i].find(vt[1])==mp3[i].end())if(in2[i]>2||!cut[i]){pii[++tot]={mp2[i][vt[0]],mp2[i][vt[1]]};if(pii[tot].first>pii[tot].second)swap(pii[tot].first,pii[tot].second);}}}else if(cut[vt[0]]){if(quick(vt[0],vt[1])){for(int i=1;i<=n;i++)if(in[i]>2&&in[i]%2==0&&	mp2[i].find(vt[0])!=mp2[i].end()&&mp2[i].find(vt[1])!=mp2[i].end()&&easyck(u[mp2[i][vt[1]]],v[mp2[i][vt[1]]],u[mp2[i][vt[0]]],v[mp2[i][vt[0]]])){pii[++tot]={mp2[i][vt[0]],mp2[i][vt[1]]};if(pii[tot].first>pii[tot].second)swap(pii[tot].first,pii[tot].second);}}else{memeset(in2,0,sizeof in2);for(int i:vtt)for(int v:e[i])if(cut[v])in2[v]++;for(int i=1;i<=n;i++)if(in[i]>2&&in[i]%2==0&&mp2[i].find(vt[0])!=mp2[i].end()&&mp2[i].find(vt[1])!=mp2[i].end()&&mp3[i].find(vt[0])==mp3[i].end()&&mp3[i].find(vt[1])==mp3[i].end())if(in2[i]>2||!cut[i]){pii[++tot]={mp2[i][vt[0]],mp2[i][vt[1]]};if(pii[tot].first>pii[tot].second)swap(pii[tot].first,pii[tot].second);}}}else{	if(at[vt[0]]!=at[vt[1]]){	for(int i=1;i<=n;i++)if(in[i]>2&&in[i]%2==0&&	mp2[i].find(vt[0])!=mp2[i].end()&&mp2[i].find(vt[1])!=mp2[i].end()&&easyck(u[mp2[i][vt[1]]],v[mp2[i][vt[1]]],u[mp2[i][vt[0]]],v[mp2[i][vt[0]]])){pii[++tot]={mp2[i][vt[0]],mp2[i][vt[1]]};if(pii[tot].first>pii[tot].second)swap(pii[tot].first,pii[tot].second);}}else{quick(vt[0],vt[1]);memeset(in2,0,sizeof in2);for(int i:vtt)for(int v:e[i])if(cut[v])in2[v]++;for(int i=1;i<=n;i++)if(in[i]>2&&in[i]%2==0&&mp2[i].find(vt[0])!=mp2[i].end()&&mp2[i].find(vt[1])!=mp2[i].end())if(!cut[i]||in2[i]>2){pii[++tot]={mp2[i][vt[0]],mp2[i][vt[1]]};if(pii[tot].first>pii[tot].second)swap(pii[tot].first,pii[tot].second);}}}sort(pii+1,pii+tot+1);printf("%lld %lld",pii[1].first,pii[1].second);}puts("");}}
}
/*
提供一个fake样例
10 14
1 2
2 3
3 4
4 1
1 5
1 6
5 7
6 7
7 8
8 9
9 10
10 7
1 7
7 9
*/