用欧拉路径判断图同构推出reverse合法性：1116T4

http://cplusoj.com/d/senior/p/SS231116D

假设我们要把 $a$ 变成 $b$，我们在 $a_i$ 和 $a_{i+1}$ 之间连边，$b$ 同理，则 $a$ 能变成 $b$ 的充要条件是两图 $A,B$ 同构。

必要性显然，因为无论如何reverse都不会改变图的形态。我们现在要证明的是图的任意欧拉路径都可以通过reverse构造出来。

考虑第一个 $a_i\ne b_i$ 的位置 $i$，设 $x=b_i,y=b_{i-1}=a_{i-1}$。在图同构是必然存在一个 $a_k=x$，且 $a_{k-1}$ 或 $a_{k+1}$ 其中一个等于 $y$。（注意 $A,B$ 同构）

如果 $a_{k+1}=y$，我们直接reverse即可。如果 $a_{k-1}=y$，我们只需要考虑 $(x,y)$ 这条边在 $A$ 中是不是桥就行。因为在 $B$ 中一定不是桥（注意到 $y$ 必然出现两次）

因为如果在 $A$ 中是桥，$B$ 中不是，说明 $A,B$ 不同构，和我们的前提冲突。

如果在 $A$ 中不是桥，说明对于这条边来说 $A,B$ 同构，说明一定存在 $i\le l\le k-1,r>k+1$ 满足 $a_l=a_r$。我们直接按 $[l,r]$ reverse即可。因此一定可以构造

#include 
#include 
#include 
#include 

using namespace std;

struct xorShift128Plus {
	unsigned long long k1, k2;
	unsigned long long gen() {
		register unsigned long long k3 = k1, k4 = k2;
		k1 = k4;
		k3 ^= k3 << 23;
		k2 = k3 ^ k4 ^ (k3 >> 17) ^ (k4 >> 26);
		return k2 + k4;
	}
	int gen(int w) {
		return gen()%w;
	}
}rnd;

const int S=5000005;
#define pb push_back
#define fi first
#define se second

int n, a[S], t[S], k, i, tot;
bool b[S]; 
int ans[S];
vector<pair<int, int> >G[S]; 

void dfs(int x) {
	for(; t[x]<G[x].size(); ){
		auto p=G[x][t[x]]; ++t[x]; 
		if(b[p.se]) continue; 
		int y=p.fi; b[p.se]=1; 
		dfs(y); 
	}
	ans[++tot]=x; 
}

void cun(int x, int y) {
	G[x].pb({y, ++k}); G[y].pb({x, k}); 
}

int main()
{
	freopen("life.in","r",stdin);
	freopen("life.out","w",stdout);
		#ifdef LOCAL
	  freopen("in.txt", "r", stdin);
	  freopen("out.txt", "w", stdout);
	#endif
	int t;
	scanf("%d%d",&n,&t);
	if(t==0) for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	else
	{
		int ra;
		scanf("%d%llu%llu",&ra,&rnd.k1,&rnd.k2);
		for(int i=1;i<=n;i++) a[i]=rnd.gen(ra)+1;
	}
	
//	cun(n+1, a[1]); cun(n+2, a[n]); 
	for(i=1; i<n; ++i) cun(a[i], a[i+1]); 
	for(i=1; i<=n+2; ++i) {
		sort(G[i].begin(), G[i].end()); 
//		reverse(G[i].begin(), G[i].end()); 
	}
	dfs(a[1]); reverse(ans+1, ans+n+1); 
	
	/*
		code here
	*/
	if(t==0)
	{
		for(int i=1;i<=n;i++) printf("%d ",ans[i]);
		printf("\n");
	}
	else
	{
		int bse=1919839,p=1000000007;
		int mul=1,res=0;
		for(int i=1;i<=n;i++,mul=1ll*mul*bse%p) res=(res+1ll*ans[i]*mul%p)%p;
		printf("%d\n",res);
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88