【hnoi2010】平面图判定

题目描述很简单：

      把一些元素划分到两个集合，其中某些元素不能再一个集合，问是否可行。

      数据组数<=100，N<=200,M<=10000；

关于集合划分的判定性问题，很容易联想到2-sat构图。

总之思想十分简单，把每个点拆分成两个点 a 和 b ，意义是这个元素在A集合或B集合。

对与两两不可以处于同一个集合的点 i 和 j ，连接ai-bj，aj-bi（无向），存在点p，ap可以到bp，那么就是矛盾的，可以理解为p如果在A集合，那么p在B集合。

      以边为点，那么将会有M2条边，思维就在这里卡住了。

      后来仔细分析了一下，发现其实在一个n个点的哈密顿回路内部，最多有n-3条边，因此，这样的n个点的图如果有超过3N-6的边，那么一定不是平面图。所以，只有在m<=3n-6的时候才需要进行判定。

      最后算法复杂度为O（N2T）；

贴代码：

program ex2;

var

a,b,c:array[0..10005] of longint;

p,d,next,f:array[0..100000] of longint;

t,task,i,j,k,n,m:longint;

ok:boolean;

procedure link(a,b:longint);

begin

inc(t);

next[t]:=d[a];d[a]:=t;p[t]:=b;

end;

procedure dfs(o:longint);

var j,k:longint;

begin

f[o]:=i;

if f[o]=f[o xor 1] then ok:=false;

if not ok then exit;

k:=d[o];j:=p[k];

while k<>0 do begin

if f[j]=0 then dfs(j);

k:=next[k];j:=p[k];

end;

end;

begin

assign(input,'input.txt');reset(input);

assign(output,'output.txt');rewrite(output);

readln(task);

for task:=1 to task do begin

readln(n,m);

fillchar(f,sizeof(f),0);

fillchar(d,sizeof(d),0);

for i:=1 to m do readln(a[i],b[i]);

for i:=1 to n do begin

read(j);c[j]:=i;

end;

t:=0;

if m>3*n-6 then writeln('NO')

else begin

for i:=1 to m do begin

a[i]:=c[a[i]];b[i]:=c[b[i]];

if a[i]>b[i] then begin

j:=a[i];a[i]:=b[i];b[i]:=j;

end;

if a[i]+1=b[i] then continue;

if (a[i]=1) and(b[i]=n) then continue;

for j:=1 to i-1 do

if ((a[j]=a[i])or(a[j]=b[i])or(b[j]=a[i])or(b[j]=b[i]))or

(not (((a[j]>a[i])and(a[j]<b[i]))xor((b[j]>a[i])and(b[j]<b[i])))) then

else begin

if b[j]=a[j]+1 then continue;

if (a[j]=1) and(b[j]=n) then continue;

link(i*2,j*2+1);

link(j*2+1,i*2);

link(i*2+1,j*2);

link(j*2,i*2+1);

end;

end;

ok:=true;

i:=0;

for j:=1 to m do begin

k:=j*2;

if f[k]=0 then begin

inc(i);dfs(k);

end;

if not ok then break;

end;

if ok then writeln('YES')

else writeln('NO');

end;

end;

close(input);close(output);

end.