SGU 172 — eXam
这道题WindyWinter牛给出的算法是并查集,实际上可以DFS解决(感谢alft…).
每个人选的两个课程之间连无向边,然后DFS时进行黑白染色,DFS树上每个结点和他的父亲节点不同色.然后考虑横向边和返祖边,如果有一条边两边的结点颜色相同则说明无解,否则将白色的考试放在一天,黑色的放在另一天就可以了…
并查集当然也没错…
注意会是一个森林,需要多次DFS…
{
SGU 172; eXam
- sqybi’s code
- DFS
}
//for my winsty
program 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;
adj[-tot] := x;
next[-tot] := head[y];
head[y] := - tot;
end;
function dfs(x: longint): boolean;
var
temp: longint;
begin
dfs := false;
temp := head[x];
while temp <> 0 do begin
if p[adj[temp]] <> 0 then begin
if p[adj[temp]] = p[x] then
exit;
end
else begin
p[adj[temp]] := 3 - p[x];
if not dfs(adj[temp]) then exit;
end;
temp := next[temp];
end;
dfs := true;
end;
begin
readln(n, m);
tot := 0;
for i:=1 to m do begin
readln(x, y);
addEdge(x, y);
end;
fillchar(p, sizeof(p), 0);
flag := true;
for i:=1 to n do
if p[i] = 0 then begin
p[i] := 1;
flag := dfs(i);
if not flag then break;
end;
if flag then begin
writeln(’yes’);
t := 0;
for i:=1 to n do
if p[i] = 1 then inc(t);
writeln(t);
for i:=1 to n do
if p[i] = 1 then write(i, ‘ ‘);
writeln;
end
else
writeln(’no’);
end.
阅读(106 次)