【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.