SPOJ 1436 — Is it a tree (code: PT07Y)
给出一个无向图,问是不是树.一个DFS完事,竟然0.4分…POJ 1308和这个只有输入格式不同.
不多解释.
{
SPOJ 1436; Is it a tree; PT07Y
- sqybi’s code
- DFS
}
//for my winsty
program 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 dfs(x, y: longint): boolean;
var
temp: longint;
begin
inc(tot);
f[x] := y;
dfs := false;
temp := head[x];
while temp <> 0 do begin
if (f[adj[temp]] <> -1) and (adj[temp] <> y) then exit;
if (adj[temp] <> y) and (not dfs(adj[temp], x)) then exit;
temp := next[temp];
end;
dfs := true;
end;
begin
readln(n, m);
if m <> n - 1 then
writeln(’NO’)
else begin
for i:=1 to m do begin
readln(x, y);
addEdge(x, y);
addEdge(y, x);
end;
fillchar(f, sizeof(f), $FF);
tot := 0;
if dfs(1, 0) and (tot = n) then
writeln(’YES’)
else
writeln(’NO’);
end;
end.
阅读(136 次)