题目描述
后缀为 contest/181/problem/1
思路分析
考试结束前30分钟才读懂题……每个单词有两个字符，其中第一个字符必须和当前的复杂词的结尾字符相同才能加上去，这不难想到需要建边。
然后我就暴力跑了一遍，然后就没有然后了……
其实就是一个欧拉路，将每一个简单词的两个字符之间建边，权值为该简单词的编号。
(T=1) 的时候是无向图，(t=2) 的时候是有向图，分开讨论就好了
关于欧拉路
无向图和有向图能成为欧拉路的都分别有两种情况
- 无向图：
1.所有点的度数全部为偶数
2.只有两个点的度数为奇数(起点和终点) - 有向图：
1.所有点出度和入度均相同
2.只有两个点出度和入度不同，且出度和入度的差值一个为 (1)，另一个为 (-1)(起点和终点)
如果是欧拉回路的话，那么无论是有向图还是无向图，都只有第一种情况成立
(Code)
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define R register
#define N 200010
using namespace std;
inline int read(){
int x = 0,f = 1;
char ch = getchar();
while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
return x*f;
}
int t,m,n,x[N],y[N],head[N],ans[N],sta[N],top,in[N],out[N],tot,cnt;
bool vis[N<<1],flag[N];
struct edge{
int to,next,id;
}e[N<<1];
int len = 1;
void addedge(int u,int v,int w){
e[++len].to = v;
e[len].id = w;
e[len].next = head[u];
head[u] = len;
}
void dfs(int u){
vis[u] = 1,cnt++;
for(R int i = head[u];i;i = e[i].next){
int v = e[i].to;
//printf("--%d--
",v);
if(vis[v])continue;
dfs(v);
}
}
void dfs1(int u,int x){
for(R int i = head[u];i;i = e[i].next){
if(vis[i])continue;
vis[i] = vis[i^1] = 1;
int v = e[i].to;
head[u] = i;//这里是个小技巧，可以避免多余的遍历，不加的话实测会T
dfs1(v,i);
i = head[u];
}
ans[++ans[0]] = e[x].id;
}
void solve1(){
for(R int i = 1;i <= n;i++){
x[i] = read(),y[i] = read();
if(!vis[x[i]])vis[x[i]] = 1,tot++;
if(!vis[y[i]])vis[y[i]] = 1,tot++;
addedge(x[i],y[i],i),addedge(y[i],x[i],-i);
in[x[i]]++,in[y[i]]++;
}
memset(vis,0,sizeof(vis));
dfs(x[1]);
//printf("%d %d
",cnt,tot);
if(cnt!=tot)return puts("NO"),void();
memset(vis,0,sizeof(vis));
for(R int i = 1;i <= n;i++){
if((in[x[i]]&1)&&!vis[x[i]])sta[++top] = x[i],vis[x[i]] = 1;
if((in[y[i]]&1)&&!vis[y[i]])sta[++top] = y[i],vis[y[i]] = 1;
}
memset(vis,0,sizeof(vis));
if(!top)dfs1(x[1],0);
else if(top==2)dfs1(sta[1],0);
else return puts("NO"),void();
puts("YES");
for(R int i = n;i;i--)printf("%d ",ans[i]);
}
void dfs2(int u,int x){
if(!flag[u])flag[u] = 1,cnt++;
for(R int i = head[u];i;i = e[i].next){
if(vis[i])continue;
vis[i] = 1;
int v = e[i].to;
head[u] = i;
dfs2(v,i);
i = head[u];
}
ans[++ans[0]] = e[x].id;
}
void solve2(){
for(R int i = 1;i <= n;i++){
x[i] = read(),y[i] = read();
if(!vis[x[i]])vis[x[i]] = 1,tot++;
if(!vis[y[i]])vis[y[i]] = 1,tot++;
addedge(x[i],y[i],i);
out[x[i]]++,in[y[i]]++;
}
memset(vis,0,sizeof(vis));
for(R int i = 1;i <= n;i++){
if(in[x[i]]!=out[x[i]]){
if(abs(in[x[i]]-out[x[i]])!=1)return puts("NO"),void();
if(!vis[x[i]])sta[++top] = x[i],vis[x[i]] = 1;
}
if(in[y[i]]!=out[y[i]]){
if(abs(in[y[i]]-out[y[i]])!=1)return puts("NO"),void();
if(!vis[y[i]])sta[++top] = y[i],vis[y[i]] = 1;
}
}
memset(vis,0,sizeof(vis));
if(!top)dfs2(x[1],0);
else if(top==2){
if(in[sta[1]]-out[sta[1]]==in[sta[2]]-out[sta[2]])return puts("NO"),void();
if(out[sta[1]]-in[sta[1]]==1)dfs2(sta[1],0);
else dfs2(sta[2],0);
}
else return puts("NO"),void();
if(cnt!=tot)return puts("NO"),void();
puts("YES");
for(R int i = n;i;i--)printf("%d ",ans[i]);
}
int main(){
freopen("merge.in","r",stdin);freopen("merge.out","w",stdout);
t = read(),m = read(),n = read();
if(t==1)solve1();
else solve2();
return 0;
}