poj3275

比较笨啊，一直在想，到底问几次绝对能知道所有的关系呢?

后来看了题解才知道，问一次最少确定一对关系…………

这就好办le，n头牛有C（2，n）个关系

现在给出m条边，以确定的关系有多少呢？直接dfs啊……

……O(nm)

 1 type link=^node;
 2      node=record
 3        po:longint;
 4        next:link;
 5      end;
 6 var w:array[0..1010] of link;
 7     sum:array[0..1010] of longint;
 8     v:array[0..1010] of boolean;
 9     n,i,m,ans,x,y:longint;
10 
11 procedure add(x,y:longint);
12   var p:link;
13   begin
14     new(p);
15     p^.next:=w[x];
16     p^.po:=y;
17     w[x]:=p;
18   end;
19 
20 procedure dfs(i:longint);
21   var p:link;
22       y:longint;
23   begin
24     p:=w[i];
25     v[i]:=true;
26     sum[i]:=1;
27     while p<>nil do
28     begin
29       y:=p^.po;
30       if not v[y] then
31       begin
32         dfs(y);
33         sum[i]:=sum[i]+sum[y];
34       end;
35       p:=p^.next;
36     end;
37   end;
38 
39 begin
40   readln(n,m);
41   for i:=1 to m do
42   begin
43     readln(x,y);
44     add(x,y);
45   end;
46   for i:=1 to n do
47   begin
48     fillchar(v,sizeof(v),false);
49     dfs(i);
50     ans:=ans+sum[i]-1;
51   end;
52   writeln(n*(n-1) div 2-ans);
53 end.

View Code