SGU 172 — eXam

Posted on 五月 27th, 2008.

这道题WindyWinter牛给出的算法是并查集,实际上可以DFS解决(感谢alft…).
每个人选的两个课程之间连无向边,然后DFS时进行黑白染色,DFS树上每个结点和他的父亲节点不同色.然后考虑横向边和返祖边,如果有一条边两边的结点颜色相同则说明无解,否则将白色的考试放在一天,黑色的放在另一天就可以了…并查集当然也没错…
注意会是一个森林,需要多次DFS…
{ SGU 172; eXam - sqybi’s code - DFS}//for my winstyprogram sgu172_sqybi;  const    nn = 200;    mm = 30000;
  var    n, m, tot, i, x, y, t: longint;    flag: boolean;    head, p: array[1..nn]of longint;    adj, next: array[-mm..mm]of longint;
  procedure addEdge(x, y: longint);    begin      inc(tot);      adj[tot] := y;      next[tot] := head[x];      head[x] := tot;      […]

Read Full Post | Make a Comment ( None so far )

SPOJ 1436 — Is it a tree (code: PT07Y)

Posted on 五月 4th, 2008.

给出一个无向图,问是不是树.一个DFS完事,竟然0.4分…POJ 1308和这个只有输入格式不同.
不多解释.
{ SPOJ 1436; Is it a tree; PT07Y - sqybi’s code - DFS}//for my winstyprogram pt07y_sqybi;  const    nn = 10000;
  var    n, m, i, x, y, tot: longint;    f, head, adj, next: array[1..nn*2]of longint;
  procedure addEdge(x, y: longint);    begin      inc(tot);      adj[tot] := y;      next[tot] := head[x];      head[x] := tot;    end;
  function […]

Read Full Post | Make a Comment ( None so far )

Liked it here?
Why not try sites on the blogroll...