1997: [Hnoi2010]Planar
Time Limit: 10 Sec
Memory Limit: 64 MB
[
Submit][
Status][
Discuss]
Description
Input
Output
Sample Input
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
Sample Output
NO YES
HINT
Source
平面图
m<=3n-6，我也不知道为什么
然后2-sat建模
ai->bj
aj->bi
判ai，aj是否在同一强连通分量
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int N = 2005;
int T,n,m,id,top,cnt,scnt,tail;
int dfn[N],low[N],inq[N],q[N],u[N*5],v[N*5],pos[N],last[N],belong[N];
struct Edge{
int to,next;
}e[N*500];
void insert( int u, int v ){
e[++cnt].to = v; e[cnt].next = last[u]; last[u] = cnt;
e[++cnt].to = u; e[cnt].next = last[v]; last[v] = cnt;
}
void tarjan( int x ){
int now = 0;
dfn[x] = low[x] = ++id;
q[++top] = x; inq[x] = 1;
for( int i = last[x]; i; i = e[i].next )
if(!dfn[e[i].to]){
tarjan(e[i].to);
low[x] = min(low[x],low[e[i].to]);
} else if( inq[e[i].to] ) low[x] = min(low[x],dfn[e[i].to]);
if( low[x] == dfn[x] ){
scnt++;
while( now != x ){
now = q[top--]; inq[now] = 0;
belong[now] = scnt;
}
}
}
void init(){
memset(last,0,sizeof(last));
memset(dfn,0,sizeof(dfn));
memset(low,0,sizeof(low));
memset(inq,0,sizeof(inq));
cnt = id = scnt = top = tail = 0;
}
bool check(){
for( int i = 1; i <= tail; i++ ) if( belong[i*2] == belong[i*2-1] ) return false;
return true;
}
int main(){
scanf("%d", &T);
while( T-- ){
scanf("%d%d", &n, &m);
init();
for( int i = 1; i <= m; i++ ) scanf("%d%d", &u[i], &v[i]);
for( int i = 1,x; i <= n; i++ ) scanf("%d", &x), pos[x] = i;
if( m > n*3-6 ){ puts("NO"); continue; }
for( int i = 1; i <= m; i++ ){
v[i] = pos[v[i]]; u[i] = pos[u[i]];
if( u[i] > v[i] ) swap(u[i],v[i]);
if( v[i]-u[i] == 1 || ( v[i] == n && u[i] == 1 )) continue;
u[++tail] = u[i]; v[tail] = v[i];
}
for( int i = 1; i <= tail; i++ )
for( int j = i+1; j <= tail; j++ )
if( (u[i]<u[j]&&u[j]<v[i]&&v[i]<v[j]) || (u[j]<u[i]&&u[i]<v[j]&&v[j]<v[i])){
insert(i*2-1,2*j); insert(2*i,2*j-1);
}
for( int i = 1; i <= 2*tail; i++ ) if( !dfn[i] ) tarjan(i);
if( check() ) puts("YES");
else puts("NO");
}
return 0;
}
