P3209 [HNOI2010]PLANAR[2_sat]

题目描述

若能将无向图G=(V,E)画在平面上使得任意两条无重合顶点的边不相交,则称G是平面图。判定一个图是否为平面图的问题是图论中的一个重要问题。现在假设你要判定的是一类特殊的图,图中存在一个包含所有顶点的环,即存在哈密顿回路。

输入输出格式

输入格式:

输入文件的第一行是一个正整数T,表示数据组数(每组数据描述一个需要判定的图)。接下来从输入文件第二行开始有T组数据,每组数据的第一行是用空格隔开的两个正整数N和M,分别表示对应图的顶点数和边数。紧接着的M行,每行是用空格隔开的两个正整数u和v( $1\le u,v\le n$),表示对应图的一条边(u,v),输入的数据保证所有边仅出现一次。每组数据的最后一行是用空格隔开的 $N$ 个正整数,从左到右表示对应图中的一个哈密顿回路:$V_1,V_2,…,V_N$,即对任意 $i≠j$ 有 $V_i≠V_j$ 且对任意 $1 \le i\le n-1 $ 有($V_i$,$V_{i-1}$ ) ∈E及( $V_1,V_n$) ∈E。输入的数据保证100%的数据满足 $T \le 100$,$3\le N\le 200$, $M\le 10000$。

输出格式:

包含T行,若输入文件的第i组数据所对应图是平面图,则在第i行输出YES,否则在第i行输出NO,注意均为大写字母

输入输出样例

输入样例#1:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
2
6 9
1 4
1 5
1 6
2 4
2 5
2 6
3 4
3 5
3 6
1 4 2 5 3 6
5 5
1 2
2 3
3 4
4 5
5 1
1 2 3 4 5

输出样例#1:

1
2
NO
YES

说明

感谢@hibiki 对题目进行修正

题解

因为是个平面图,所以不在哈密顿回路上的边,要么在环内,要么在环外,这时候,一些边就会有冲突,连边就好。

然后一直只想到 $m^2$ 的方法,看题解,平面图的性质:边数小于等于 $3n−6$ ,可以用欧拉定理证,点数+分成的块数-边数=2。

每条边都属于2个块,要三条边才能构成一个块,那么2×边数<=3×分成的块数,然后带入上面那个式子,就可以解出来了。

所以可以暴力建边,然后缩点去判在不在一个环内。

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
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
//rp++
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int qmax(int &x,int y) {if (x<y) x=y;}
int qmin(int &x,int y) {if (x>y) x=y;}
int read()
{
char s;
int k=0,base=1;
while((s=getchar())!='-'&&s!=EOF&&!(isdigit(s)));
if(s=='-')base=-1,s=getchar();
while(isdigit(s)){k=k*10+(s^'0');s=getchar();}
return k*base;
}
inline void write(int x)
{
static char cnt,num[15];cnt=0;
if (!x)
{
putchar('0');
return;
}
for (;x;x/=10) num[++cnt]=x%10;
for (;cnt;putchar(num[cnt--]+48));
}
const int maxm=7e4+100;
const int maxn=210;
int T,n,m,X,Y,top;
struct edge
{
int x,y;
} g[20100];
int to[maxm],ne[maxm],po[1200],id;
int b[maxn],a[maxn];
inline void add(int x,int y)
{
id++;to[id]=y;ne[id]=po[x];po[x]=id;
}
int dfn[1200],low[1200],scc[1200],flag,sccid;
stack<int> S;
void tarjan(int x)//缩点
{
S.push(x);
dfn[x]=++top;
low[x]=dfn[x];
int y=0;
for (int i=po[x];i;i=ne[i])
{
y=to[i];
if (dfn[y]==0)
{
tarjan(y);
if (!flag) return;
qmin(low[x],low[y]);
} else
if (scc[y]==0) qmin(low[x],dfn[y]);
}
if (low[x]==dfn[x])
{
++sccid;
while (S.top()!=x)
{
scc[S.top()]=sccid;
if (scc[(S.top()+m)%(2*m)]==sccid)
{
flag=0;
return;
}
S.pop();
}
scc[S.top()]=sccid;
S.pop();
}
}
int main()
{
T=read();
while (T--)
{
id=0;top=0;flag=1;
sccid=0;n=read();m=read();
if (m>3*n-6)
{
for (int i=1;i<=m;i++) X=read(),Y=read();
for (int i=1;i<=n;i++) X=read();
printf("NO\n");
continue;
}
while (!S.empty()) S.pop();
memset(dfn,0,sizeof(dfn));
memset(scc,0,sizeof(scc));
memset(po,0,sizeof(po));
for (int i=1;i<=m;i++)
{
g[i].x=read();g[i].y=read();
}//i,i+m
for (int i=1;i<=n;i++)
{
a[i]=read();b[a[i]]=i;
}
for (int i=1;i<m;i++)
{//暴力连边
X=g[i].x;Y=g[i].y;
if (abs(b[X]-b[Y])==1||(b[X]==1&&b[Y]==n)||(b[X]==n&&b[Y]==1)) continue;
int fr,ed;
fr=min(b[X],b[Y]);
ed=max(b[X],b[Y]);
for (int j=i+1;j<=m;j++)
{
X=g[j].x;Y=g[j].y;
if (abs(b[X]-b[Y])==1||(b[X]==1&&b[Y]==n)||(b[X]==n&&b[Y]==1)) continue;
if (g[j].x==g[i].x||g[j].y==g[i].x||g[i].y==g[j].y||g[i].y==g[j].x) continue;
if ((fr<b[X]&&b[X]<ed)^(fr<b[Y]&&b[Y]<ed))
{
add(i,j+m);add(j,i+m);
add(j+m,i);add(i+m,j);
}
}
}
for (int i=1;i<=2*m;i++)
{
if (dfn[i]==0) tarjan(i);
if (!flag) break;
}
if (flag)
{
for (int i=1;i<=m;i++)
if (scc[i]==scc[i+m])
{
flag=0;
break;
}
}
if (!flag) printf("NO\n"); else printf("YES\n");
}
return 0;
}