2023-11-13第十二周
11-13 缩点
上周周末去ccpc深圳打了次星。四道签到题就写了一题，打的时候都有种要爆0的感觉。平时在学校还是打的太安逸了，觉得自己打的还挺好。确实是缺少拷打。没办法，菜就多练。
上周看了下连通性的一些知识点，今天的目标就是把缩点和2-sat的知识点学了，再去补一套ABC。如果缩点学的慢的话就是缩点加一套ABC。
先学缩点，看看洛谷的例题
P3387 【模板】缩点 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
缩点的正解应该也是用tarjin写的，不过我翻题解的时候看见一个我觉得很有意思的写法。研究了一下。
思路主要是在跑dfs的时候对点的状态进行标记。一个点有三种状态:已经搜索完了(负)、正在搜索（正）、没有搜索（0）。在dfs中，u是v的父节点，如果v的状态是正在搜索，那么v和u在同一个强连通分量中。可以用并查集记录他们在那个强连通分量中。注意合并父节点的时候一定要先被搜索到的节点作为祖先节点，因为在深搜中，后被搜索到的节点 搜索先结束，如果用后被搜索到的节点 他的搜索一结束，这个强连通分量的搜索就结束了，所以不对。
题解链接:题解 P3387 【模板】缩点 - Warriors_Cat 的博客 - 洛谷博客 (luogu.com.cn)
我的AC代码:
#include <bits/stdc++.h>
#define int long long
#define endl '\n';
using namespace std;
const int N = 1e4 + 10;
int n,m;
int a[N];
int c[N];
vector<int> G[N];
int vis[N];
int fa[N];
int du[N];
int s[N];
struct ed{
int u,v;
}edge[100010];
int Find(int x){
return x==fa[x] ? x : fa[x]=Find(fa[x]);
}
void dfs(int u){
for(auto v:G[u]){
if(!vis[v]){
vis[v]=vis[u]+1; //要根据vis的值判断那个点是先被访问的
dfs(v);
}
int tu=Find(u),tv=Find(v);
if(vis[tv]>0){ //正在被搜索
if(vis[tv]<vis[tu]) fa[tu]=tv;
else fa[tv]=tu;
}
}
vis[u]=-1; //搜索结束
}
void solve(){
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=0;i<m;i++){
cin>>edge[i].u>>edge[i].v;
G[edge[i].u].push_back(edge[i].v);
}
for(int i=1;i<=n;i++) fa[i]=i;
for(int i=1;i<=n;i++) if(!vis[i]) dfs(i);
for(int i=1;i<=n;i++){
G[i].clear();
c[Find(i)]+=a[i];
}
for(int i=0;i<m;i++){
int ta=Find(edge[i].u);
int tb=Find(edge[i].v);
if(ta==tb) continue;
G[ta].push_back(tb);
du[tb]++;
}
//然后跑拓扑
int ans=0;
queue<int> pp;
for(int i=1;i<=n;i++)
if(du[i]==0&&i==fa[i]){
pp.push(i);
s[i]=c[i];
ans=max(ans,s[i]);
}
while(pp.size()){
int u=pp.front();
pp.pop();
for(auto v:G[u]){
s[v]=max(s[v],s[u]+c[v]);
ans=max(ans,s[v]);
if(--du[v]==0) pp.push(v);
}
ans=max(ans,s[u]);
}
cout<<ans<<endl;
}
signed main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int T=1;
//cin>>T;
while(T--)solve();
return 0;
}
用了并查集所以应该会比tarjin多一个log。
歪门邪道学完了该去看正解了。
看了一下题解的意思。好像就是用tarjin求出low和dfn，如果dfn[i]==low[i]那么i就是一个强连通分量的根结点，在dfs的过程中将遍历到的点压入栈，在两个强连通分量直接的点就在一个强连通分量中？好像是这个意思。
又看了一下应该没错。low[i]存的其实就是他能到的点(包括他自己)的最小的时间搓，如果low[i]==dfn[i]说明以i为根结点往下必有一个环。
tarjan算法求scc & 缩点 - 菜鸡mk - 博客园 (cnblogs.com)
这个链接讲的很详细
,当访问到某一个在栈中的节点的时候，我们要用这个节点的dfn值来更新其他节点，所以有low[u]=min(low[u],dfn[v])
在之前用tarjin算法求桥和割点的时候，只要v被访问过且v不是u的父节点，我们就可以用low[u]=min(low[u],dfn[v]),但是在缩点这里不一样。这里的条件是v被访问过且v在栈中。因为如果v不在栈中又被访问过，说明他被缩成了另一个点，我们就不能用他dfn的值来更新u的low。（想这个东西想了几个小时，折磨啊）
AC代码:
#include <bits/stdc++.h>
#define int long long
#define endl '\n';
using namespace std;
const int N = 1e4 + 10;
int n,m;
int a[N],du[N],s[N];
int fa[N];
int dfn[N],low[N];
int dfs_clock;
stack<int> path;
vector<int> G[N];
bool vis[N];
struct ed{
int u,v;
}edge[100010];
void tarjin(int u){
path.push(u);
dfn[u]=low[u]=++dfs_clock;
vis[u]=true;
for(auto v:G[u]){
if(!dfn[v]){
tarjin(v);
low[u]=min(low[u],low[v]);
}else if(vis[v]){
low[u]=min(low[u],dfn[v]);
}
}
if(dfn[u]==low[u]){
while(path.size()){
if(path.top()==u){
path.pop();
vis[u]=false;
break;
}
vis[path.top()]=false;
fa[path.top()]=u;
a[u]+=a[path.top()];
path.pop();
}
}
}
void solve(){
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a[i];
fa[i]=i;
}
for(int i=0;i<m;i++){
cin>>edge[i].u>>edge[i].v;
G[edge[i].u].push_back(edge[i].v);
}
for(int i=1;i<=n;i++)
if(!dfn[i]) tarjin(i);
int ans=0;
for(int i=1;i<=n;i++) G[i].clear();
for(int i=0;i<m;i++){
int u=fa[edge[i].u];
int v=fa[edge[i].v];
if(u==v) continue;
du[v]++;
G[u].push_back(v);
}
queue<int> que;
for(int i=1;i<=n;i++)
if(fa[i]==i&&du[i]==0){
que.push(i);
s[i]=a[i];
ans=max(ans,s[i]);
}
while(que.size()){
int u=que.front();que.pop();
for(auto v:G[u]){
s[v]=max(s[v],s[u]+a[v]);
ans=max(ans,s[v]);
if(--du[v]==0) que.push(v);
}
}
cout<<ans<<endl;
}
signed main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int T=1;
//cin>>T;
while(T--)solve();
return 0;
}
看了眼2-SAT好像就是建图缩点，还是先把2-SAT看了吧，ABC写了估计也补不完。
看不完，明天继续。今天题数又不够了。
11-14 2-SAT
P4782 【模板】2-SAT - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
#include <bits/stdc++.h>
#define int long long
#define endl '\n';
using namespace std;
const int N = 2e6 + 10;
int n,m;
vector<int> G[N];
int fa[N] , dfn[N] , low[N];
int scc[N] , cnt;
bool vis[N];
int dfs_clock;
stack<int> path;
void tarjin(int u){
dfn[u]=low[u]=++dfs_clock;
path.push(u);
vis[u]=true;
for(auto v:G[u]){
if(!dfn[v]){
tarjin(v);
low[u]=min(low[u],low[v]);
}else if(vis[v]){
low[u]=min(low[u],dfn[v]);
}
}
if(dfn[u]==low[u]){
scc[u]=++cnt;
while(path.size()){
int x=path.top();path.pop();
fa[x]=u;
scc[x]=scc[u];
vis[x]=false;
if(x==u) break;
}
}
}
void solve(){
cin>>n>>m;
for(int i=0;i<m;i++){
int x,y,a,b;
cin>>x>>a>>y>>b;
if(a==1&&b==1){
G[x+n].push_back(y);
G[y+n].push_back(x);
}else if(a==1&&b==0){
G[x+n].push_back(y+n);
G[y].push_back(x);
}else if(a==0&&b==1){
G[x].push_back(y);
G[y+n].push_back(x+n);
}else if(a==0&&b==0){
G[x].push_back(y+n);
G[y].push_back(x+n);
}
}
for(int i=1;i<=n*2;i++) fa[i]=i;
for(int i=1;i<=2*n;i++)
if(!dfn[i]) tarjin(i);
for(int i=1;i<=n;i++){
if(fa[i]==fa[i+n]){
cout<<"IMPOSSIBLE"<<endl;
return;
}
}
cout<<"POSSIBLE"<<endl;
for(int i=1;i<=n;i++){
if(scc[i]<scc[i+n]) cout<<"1 ";
else cout<<"0 ";
}
}
signed main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int T=1;
//cin>>T;
while(T--)solve();
return 0;
}
其实还挺简单的，就是根据题目条件连边，判断有没有冲突的(在同一个强连通分量中)。题目有用到拓扑排序的dfs实现的知识点，要看看才能懂在tarjin算法中顺便求拓扑序时怎么做到的。
再写一题
#include <bits/stdc++.h>
#define int long long
#define endl '\n';
using namespace std;
const int N = 1e5 + 10;
int n,m;
vector<int> G[N];
int fa[N] , dfn[N] , low[N];
int scc[N] , cnt;
bool vis[N];
int dfs_clock;
stack<int> path;
void tarjin(int u){
dfn[u]=low[u]=++dfs_clock;
path.push(u);
vis[u]=true;
for(auto v:G[u]){
if(!dfn[v]){
tarjin(v);
low[u]=min(low[u],low[v]);
}else if(vis[v]){
low[u]=min(low[u],dfn[v]);
}
}
if(dfn[u]==low[u]){
scc[u]=++cnt;
while(path.size()){
int x=path.top();path.pop();
fa[x]=u;
scc[x]=scc[u];
vis[x]=false;
if(x==u) break;
}
}
}
void init(){
for(int i=1;i<=2*n;i++){
G[i].clear();
fa[i]=i;
dfn[i]=low[i]=0;
scc[i]=0;
cnt=0;
vis[i]=false;
dfs_clock=0;
}
while(path.size()) path.pop();
}
void solve(){
cin>>n>>m;
init();
for(int i=0;i<m;i++){
string c1,c2;
cin>>c1>>c2;
int a=0,b=0;
if(c1[0]=='m') a=1;
if(c2[0]=='m') b=1;
int x=0,y=0;
for(int i=1;i<c1.size();i++) x=x*10+c1[i]-'0';
for(int i=1;i<c2.size();i++) y=y*10+c2[i]-'0';
if(a==1&&b==1){
G[x+n].push_back(y);
G[y+n].push_back(x);
}else if(a==1&&b==0){
G[x+n].push_back(y+n);
G[y].push_back(x);
}else if(a==0&&b==1){
G[x].push_back(y);
G[y+n].push_back(x+n);
}else if(a==0&&b==0){
G[x].push_back(y+n);
G[y].push_back(x+n);
}
}
for(int i=1;i<=2*n;i++)
if(!dfn[i]) tarjin(i);
for(int i=1;i<=n;i++){
if(fa[i]==fa[i+n]){
cout<<"BAD"<<endl;
return;
}
}
cout<<"GOOD"<<endl;
}
signed main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int T=1;
cin>>T;
while(T--)solve();
return 0;
}
在写一题，刚开始我也犯蠢拆了四个点。后面才反应过来对于同一种材料的两种菜其实就是像前面那题0，1的关系。两道题其实没有什么区别。
....晚上把职规的计划书写了
写完开工，本来说写套ABC的。蓝桥杯又要报名了，我先研究一下以前的题看看是报A组还是报B组。
打A组拿不到国一好像也没啥用，还是打B吧。
写写上个星期那场没打的ABC。有点晚了，能写多少写多少。
AtCoder Beginner Contest 328 - tiumop 的博客 - 洛谷博客 (luogu.com.cn)
写完D，明早继续。
11-15
今天状态不是很好。好像有点着凉。
把昨天ABC剩的E、F写了。带权并查集的写法还是不熟。要翻资料。
AtCoder Beginner Contest 328 - tiumop 的博客 - 洛谷博客 (luogu.com.cn)
11-16 欧拉图
在思维导图上是个铜算法，我看实现好像还挺复杂的。
欧拉图
本页面将简要介绍欧拉图的概念、实现和应用。
定义
- 欧拉回路：通过图中每条边恰好一次的回路
- 欧拉通路：通过图中每条边恰好一次的通路
- 欧拉图：具有欧拉回路的图
- 半欧拉图：具有欧拉通路但不具有欧拉回路的图
看了下思路，我就直接套板写了。
P1127 词链 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
这题其实只要找到欧拉通路就行了不需要找欧拉回路。
我套的板子
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
using namespace std;
const int N = 5000, M = 50007, INF = 0x3f3f3f3f;
typedef pair<int,int> PII;
int n, m;
int d[N];
int g[N][N];
int ans[M], cnt;
void dfs(int x){
for(int i = 1;i <=500 ;i++){
if(g[x][i]){
g[x][i]-- , g[i][x]--;
dfs(i);
}
}
ans[++ cnt]=x;
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
int x,y;
scanf("%d%d",&x,&y);
g[x][y]++,g[y][x]++;
d[x]++,d[y]++;
}
int start=1;
while(!d[start]) start++;
for(int i=1;i<=500;i++){
if(d[i]%2){
start=i;
break;
}
}
dfs(start);
for(int i=cnt;i;i--)
printf("%d\n",ans[i]);
return 0;
}
板子没啥用，自己搓了半天，有一组数据过不了，什么什么too short感觉也挺抽象的。尽力了，真不知道哪错了。
#include <bits/stdc++.h>
#define int long long
#define endl '\n';
using namespace std;
const int N = 1010;
string s[N];
int n;
int in[30],out[30];
int fa[30],vis[30];
bool f[N];
int head[N],to[N],nex[N];
string w[N];
int cnt;
int Find(int x){
return x==fa[x] ? x:fa[x]=Find(fa[x]);
}
void add(int u,int v,string wi){
w[cnt]=wi;
to[cnt]=v;
nex[cnt]=head[u];
head[u]=cnt++;
}
vector<string> path;
bool dfs(int u){
if(path.size()==n){
return true;
}
for(int i=head[u];~i;i=nex[i]){
if(f[i]) continue;
path.push_back(w[i]);
f[i]=true;
if(dfs(to[i])) return true;
path.pop_back();
f[i]=false;
}
return false;
}
int cmp(string a,string b){
return a>b;
}
void solve(){
memset(head,-1,sizeof head);
cin>>n;
for(int i=1;i<=n;i++) cin>>s[i];
sort(s+1,s+1+n,cmp);
int num=0;
for(int i=1;i<=n;i++){
int star=s[i][0]-'a';
int last=s[i][s[i].size()-1]-'a';
if(!vis[star]){
num++;
vis[star]=true;
fa[star]=star;
}
if(!vis[last]){
num++;
vis[last]=true;
fa[last]=last;
}
int ta=Find(star),tb=Find(last);
if(ta!=tb){
fa[ta]=tb;
num--;
}
add(star,last,s[i]);
//cout<<star<<" "<<last<<" "<<s[i]<<endl;
in[last]++;
out[star]++;
}
if(num!=1){
cout<<"***"<<endl;
return;
}
int starindex=-1;
int cntin=0,cntout=0;
for(int i=0;i<26;i++){
if(starindex==-1) starindex=i;
if(out[i]-in[i]==1){
cntin++;
starindex=i;
}
else if(in[i]-out[i]==1) cntout++;
else if(abs(out[i]-in[i])>1){
cout<<"***"<<endl;
return;
}
}
if(cntin>1||cntout>1){
cout<<"***"<<endl;
return;
}
dfs(starindex);
if(path.size()!=n){
cout<<"***"<<endl;
return;
}
for(int i=0;i<n;i++)
cout<<path[i]<<"."[i==n-1];
cout<<endl;
}
signed main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int T=1;
//cin>>T;
while(T--)solve();
return 0;
}
好吧我找到了。我起点弄错了。有的点没出现过就不能拿来当起点。
修改前：
for(int i=0;i<26;i++){
if(starindex==-1) starindex=i; //修改前
if(out[i]-in[i]==1){
cntin++;
starindex=i;
}
else if(in[i]-out[i]==1) cntout++;
else if(abs(out[i]-in[i])>1){
cout<<"***"<<endl;
return;
}
}
修改后:
就改了一个判断条件。
for(int i=0;i<26;i++){
if(starindex==-1&&vis[i]) starindex=i; //修改后
if(out[i]-in[i]==1){
cntin++;
starindex=i;
}
else if(in[i]-out[i]==1) cntout++;
else if(abs(out[i]-in[i])>1){
cout<<"***"<<endl;
return;
}
}
好恶心好恶心好恶心好恶心
题解里面好像有人讨论，我这种找起点的方法是错的。我自己想了下应该没问题，如果out[i]-in[i]1那这个点一定要是起点。如果找不到out[i]-in[i]1的点，说明图成环，那就拿最小的点作为起点。
第二题
P1333 瑞瑞的木棍 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)跟上面那题差不多，就是从有向图变成了无向图。而且没有要求按照字典序输出。
#include <bits/stdc++.h>
#define int long long
#define endl '\n';
using namespace std;
const int N = 5e5 + 10;
int fa[N],vis[N],du[N];
bool f[N];
int head[N],to[N],nex[N];
int cnt;
int Find(int x){
return x==fa[x] ? x:fa[x]=Find(fa[x]);
}
void add(int u,int v){
to[cnt]=v;
nex[cnt]=head[u];
head[u]=cnt++;
}
map<string,int> col;
vector<pair<string,string>> colpath;
bool dfs(int u,int deepth){
if(deepth==colpath.size()){
return true;
}
for(int i=head[u];~i;i=nex[i]){
if(f[i]) continue;
f[i]=true;
if(dfs(to[i],deepth+1)) return true;
f[i]=false;
}
return false;
}
void solve(){
memset(head,-1,sizeof head);
string l,r;
while(cin>>l>>r){
if(col.find(l)==col.end()) col[l]=col.size()+1;
if(col.find(r)==col.end()) col[r]=col.size()+1;
colpath.push_back({l,r});
}
int num=0;
for(int i=0;i<colpath.size();i++){
int star=col[colpath[i].first];
int last=col[colpath[i].second];
if(!vis[star]){
num++;
vis[star]=true;
fa[star]=star;
}
if(!vis[last]){
num++;
vis[last]=true;
fa[last]=last;
}
int ta=Find(star),tb=Find(last);
if(ta!=tb){
fa[ta]=tb;
num--;
}
add(star,last);
add(last,star);
//cout<<star<<" "<<last<<" "<<s[i]<<endl;
du[star]++;
du[last]++;
}
if(num!=1){
cout<<"Impossible"<<endl;
return;
}
int starindex=-1;
int cntdu=0;
for(int i=1;i<=col.size();i++){
if(starindex==-1&&vis[i]) starindex=i;
if(du[i]&1){
cntdu++;
starindex=i;
}
}
if(cntdu!=0&&cntdu!=2){
cout<<"Impossible"<<endl;
return;
}
if(dfs(starindex,0)){
cout<<"Possible"<<endl;
}else{
cout<<"Impossible"<<endl;
}
}
signed main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int T=1;
//cin>>T;
while(T--)solve();
return 0;
}
wa一组 tle一组，喜题80分的好成绩。
map改unordered_map,不超时了但是还是wa了一组。
AC代码:
#include <bits/stdc++.h>
#define int long long
#define endl '\n';
using namespace std;
const int N = 5e5 + 10;
int fa[N],vis[N],du[N];
bool f[N];
int head[N],to[N],nex[N];
int cnt;
int Find(int x){
return x==fa[x] ? x:fa[x]=Find(fa[x]);
}
void add(int u,int v){
to[cnt]=v;
nex[cnt]=head[u];
head[u]=cnt++;
}
unordered_map<string,int> col;
vector<pair<string,string>> colpath;
void solve(){
memset(head,-1,sizeof head);
string l,r;
while(cin>>l>>r){
if(col.find(l)==col.end()) col[l]=col.size()+1;
if(col.find(r)==col.end()) col[r]=col.size()+1;
colpath.push_back({l,r});
}
int num=0;
for(int i=0;i<colpath.size();i++){
int star=col[colpath[i].first];
int last=col[colpath[i].second];
if(!vis[star]){
num++;
vis[star]=true;
fa[star]=star;
}
if(!vis[last]){
num++;
vis[last]=true;
fa[last]=last;
}
int ta=Find(star),tb=Find(last);
if(ta!=tb){
fa[ta]=tb;
num--;
}
add(star,last);
add(last,star);
//cout<<star<<" "<<last<<" "<<s[i]<<endl;
du[star]++;
du[last]++;
}
if(num>1){
cout<<"Impossible"<<endl;
return;
}
int starindex=-1;
int cntdu=0;
for(int i=1;i<=col.size();i++){
if(starindex==-1&&vis[i]) starindex=i;
if(du[i]&1){
cntdu++;
starindex=i;
}
}
if(cntdu!=0&&cntdu!=2){
cout<<"Impossible"<<endl;
return;
}
cout<<"Possible"<<endl;
}
signed main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int T=1;
//cin>>T;
while(T--)solve();
return 0;
}
没懂啊。把判断连通块数量那里的num!=1改成num>1就对了就是说连通块数量有可能等于0?
应该是，木棍数量有可能为0，连通块数量为0，此时答案应该为POSSIBLE。
写第三题的时候突然写懵掉了，回头看我这个第二题代码好像还是有问题的。在跑dfs的时候有一条边用两次的可能导致结果有错。
第三题:
P1341 无序字母对 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
这题题面很短。而且明显比前面两题都要简单。本来想用邻接表写的，发现特别折磨。还是矩阵大法简单；
吐了，这题写的比上面两题还久。
#include <bits/stdc++.h>
#define int long long
#define endl '\n';
using namespace std;
const int N = 500;
int board[N][N];
int fa[N] , du[N];
bool vis[N];
int n;
deque<char> ans;
int Find(int x){
return x==fa[x] ? x : fa[x]=Find(fa[x]);
}
void dfs(int u){
for(int i=0;i<256;i++){
if(board[u][i]){
board[u][i]--;
board[i][u]--;
dfs(i);
}
}
ans.push_front(u);
}
void solve(){
cin>>n;
int num=0;
for(int i=0;i<256;i++) fa[i]=i;
for(int i=0;i<n;i++){
string s;
cin>>s;
board[s[0]][s[1]]++;
board[s[1]][s[0]]++;
if(!vis[s[0]]) num++;
vis[s[0]]=true;
if(!vis[s[1]]) num++;
vis[s[1]]=true;
du[s[0]]++;
du[s[1]]++;
int ta=Find(s[0]);
int tb=Find(s[1]);
if(ta!=tb){
num--;
fa[ta]=tb;
}
}
// for(int i=0;i<256;i++)
// if((i>='A'&&i<='Z')||(i>='a'&&i<='z'))
// cout<<fa[i]<<endl;
if(num>1){
cout<<"No Solution"<<endl;
return;
}
int starindex=-1;
int cnt_du=0;
vector<char> path;
for(int i=0;i<256;i++){
if(starindex==-1&&vis[i]) starindex=i;
if(du[i]&1){
cnt_du++;
path.push_back(i);
}
}
sort(path.begin(),path.end());
if(path.size())starindex=path.front();
if(cnt_du!=0&&cnt_du!=2){
cout<<"No Solution"<<endl;
return;
}
dfs(starindex);
for(auto v:ans) cout<<v;
}
signed main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int T=1;
//cin>>T;
while(T--)solve();
return 0;
}
第二题不用求路径只用求行不行，被我混过去了。第一题写的时候也是想当然，莫名其妙就蒙过去了，其实不太懂。搞得写第三题的时候各种出问题。第一题我写的时候那个路径是正着存的，但是在第三题这里就必须反着存才不会出错。
欧拉图写到现在。解决的主要问题就是n条什么什么东西能不能串成一串。
11-17
昨天写第三题的时候发现自己前面两题的写法都是歪的。被我写成的优化过的爆搜。去看了眼题解又去看了眼板子。题目长得不一样但是思路都是一样的，就是深搜删边，搜完子节点后再把父节点放进答案数组。如果要求要字典序最小的，建图的时候就要按字典序加边。不然的话随便怎么加。求不求字典序最小的区别只有建图加边的区别。