【usaco 2013 Mar Bronze】種類配分

1763.【usaco 2013 Mar Bronze】種類配分(Breed Assignment)(assign.pas/cpp)(File IO):input:assign.in output:assign.out
時間制限:
1000 msのスペース制限:
262144 KB具体的な制限
Goto ProblemSet
タイトルの説明
タイトル:
農夫のジョンはN匹の乳首を持っていて、このN匹の乳牛はそれぞれ3つの種類に属しています:A、B、C.しかし不幸なことに、ジョンは乳牛ごとにどの種類に属しているのか忘れてしまった.彼はK個の乳牛の関係しか覚えていない.例えば、彼は乳牛1と乳牛2が同じ種類であるか、乳牛1と乳牛5が異なる種類であることを覚えている.
問題の説明:
このKの関係を与えて、ジョンがこのN匹の乳牛の可能な種類分布状況が全部で何種類あるかを計算するのを助けてください.△K個の関係自体が矛盾している場合、答えは0です.
検索時に現在のポイントが同じ種類に合っているかどうかを判断するには一緒にいなければならず、異なる種類は一緒にいられない.

var
  f:array[0..15,0..15] of longint;
  b,t:array[0..100] of longint;
  k,i,j,n,ans,x,y,l:longint;
  ch:char;

function check(x:longint):boolean;
var
  i:longint;
begin
  check:=false;
  for i:=1 to l do
    if t[i]=x then exit(true);
end;

function tr(x,p,s:longint):boolean;
var
  i:longint;
begin
  tr:=false;
  for i:=1 to x do
    if ((f[t[i],p]=1) and (b[i]=s)) or ((f[t[i],p]=2) and (b[i]<>s)) then exit(true);
end;

procedure dfs(dep:longint);
var
  i:longint;
begin
  if dep>l then begin inc(ans);exit; end;
  for i:=1 to 3 do
     if not tr(dep-1,t[dep],i) then
       begin
         inc(j);
         b[j]:=i;
         dfs(dep+1);
         b[j]:=0;
         dec(j);
       end;
end;

begin
  assign(input,'assign.in'); reset(input);
  assign(output,'assign.out');rewrite(output);
  readln(n,k);
  l:=0; j:=0;
  for i:=1 to k do
    begin
      readln(ch,x,y);
      if ch='D' then
        begin
          f[x,y]:=1;
          f[y,x]:=1;
        end
      else
        begin
          f[x,y]:=2;
          f[y,x]:=2;
        end;
       if not check(x) then begin inc(l);t[l]:=x;end;
       if not check(y) then begin inc(l);t[l]:=y;;end;
    end;
  dfs(1);
  for i:=1 to n-l do
    ans:=ans*3;
  writeln(ans);
  close(input);close(output);
end.