来自"NOCOW"

BFS,染色,判断是否染过,如果染过且与要染的颜色相同就继续染下一个,否则输出-1

---

直接搜索判断

program cao;
const
  maxn=100;
 
var
  map:array[0..maxn,0..maxn] of boolean;
  flag,color:array[0..maxn] of boolean;
  a,b,c,d,e,f,g,h,i,j,k,l,n,m,p,q:longint;
 
procedure search(v:longint;c:boolean);
var
  i:longint;
begin
  if flag[v] then
  begin
    if color[v]<>c then
    begin
      writeln(-1);
      halt;
    end;
    exit;
  end;
  flag[v]:=true;
  color[v]:=c;
  for i:=1 to n do
    if map[i,v] then
      search(i,not(c));
end;
 
begin
  read(n);
  for i:=1 to n do
  begin
    while not(seekeof) do
    begin
      read(a);
      if a=0 then break;
      map[i,a]:=true;
      map[a,i]:=true;
    end;
  end;
 
  for i:=1 to n do
    if flag[i]=false then search(i,false);
  for i:=1 to n do
    if color[i]=true then write(1) else write(0);
  writeln;
end.

http://www.withflying.com/?p=142

http://www.withflying.com

---

爱生活，爱SPFA。--Wecing 16:10 2010年6月20日 (CST)

---

因为城堡1只能是红色 所以与城堡1接壤的必须是蓝色 使用bfs一层一层染下去 直到全部染完或者在中间有冲突直接halt掉。

program cyd;
  var
    b:array[1..100,0..500]of integer;
    d,c:array[1..100]of integer;
    p:array[1..100]of boolean;
    i,j,k,l,m,n,a,head,tail,now:longint;
  begin
    readln(n);
    for i:=1 to n do
      begin
        read(a);
        while a<>0 do
          begin
            inc(b[i,0]);
            b[i,b[i,0]]:=a;
            inc(b[a,0]);
            b[a,b[a,0]]:=i;
            read(a);
          end;
      end;
    head:=1; tail:=1; d[1]:=1;
    c[1]:=0; p[1]:=true;
    while head<=tail do
      begin
        now:=d[head];
        k:=1-c[now];
        for i:=1 to b[now,0] do
          if not p[b[now,i]] then
            begin
              p[b[now,i]]:=true;
              c[b[now,i]]:=k;
              inc(tail);
              d[tail]:=b[now,i];
            end else if c[b[now,i]]<>k then begin writeln(-1); halt; end;
        inc(head);
      end;
    for i:=1 to n do write(c[i]);
  end.