1019 集合论与图论
题目描述 Description
集合论与图论对于小松来说是比数字逻辑轻松，比数据结构难的一门专业必修课。虽然小松在高中的时候已经自学过了离散数学中的图论，组合，群论等知识。但对于集合论，小松还是比较陌生的。集合论的好多东西也涉及到了图论的知识。
在第四讲的学习中，小松学到了“有序对”这么一个概念，即用<x, y>表示有序对x和y。要注意的是有序对<x, y>不等于有序对<y, x>。对于一个有序对集合R={<x,y>, <y, z>, <x, z>，……}，我们说R是传递的，当且仅当他满足下面的性质：
红色字体用直观的语言描述是：如果存在<x, y>∈R，<y, z>∈R，那么一定存在<x, z>∈R。
这里集合R可以对应到一个有向图G，有序对<x ,y>对应到了G中的一条有向边。 你现在的任务是，对于任意给定的一个简单有向图G（同一有向边不出现两次），判断G是否具有传递性。
输入描述 Input Description
输入文件set.in第一行包含测试数据的个数T(1<=T<=10)。接下来T组测试数据，每组测试数据第一行包含两个个整数n和m（1<=n<=1000, n<=m<=100000），表示G中元素个数和有向边的个数，接下来的m行每行2个整数x, y（1<=x,y<=n）表示x与y之间有一条有向边连接。
输出描述 Output Description
对于每组数据，如果G是传递的，你需要向输出文件set.out输出一行”Yes”, 否则输出一行”No”。
样例输入 Sample Input
2
3 3
1 2
1 3
2 3
4 5
1 2
1 3
1 4
2 3
3 4
样例输出 Sample Output
Yes
No
数据范围及提示 Data Size & Hint
有30%满足1<=n<=100, 1<=m<=10000;
有100%的数据满足1<=n<=1000, 1<=m<=100000;
个人解法：
我真的好想想一个O(n)的算法，然后发现完全不必要。
于是就按照题目给的范围来做了。
首先如果<a,b>，且<b,c>，那么a是可以到c的，这个时候如果没有<a,c>那么R就不是传递的。
所以我们的任务就是对于某一个点x，判断是否存在一个点y，使得x到y没有边，但是x可以到达y。
如果存在，那么R就是不传递的。如果对于所有的点都判断完了，仍然符合要求，那么R就是传递的。
更有趣的是不用写hash——只有1000*1000的表。
正如楼下所说，开一个邻接链表，再开一个邻接矩阵。
至于判断，我们可以用BFS跑完一张图。
对于一组数据，总的复杂度是O(n^2)。
代码如下：
type
inf=record
x,next:longint;//邻接链表的边
end;
var
Arr,Arrmap:array[1..1000] of longint;//Arr是BFS的队列，Arrmap是邻接链表存图的数组
map:array[1..1000,1..1000] of boolean;//邻接矩阵
Arre:array[1..100000] of inf;//邻接链表的边
Vis:array[1..1000] of boolean;//BFS是判断是否遍历过
T,vt,vp,i,n,m,top:longint;
flag:boolean;//判断R是否传递
procedure ins(f,s:longint);//插入一条边
begin
inc(top);
Arre[top].x:=s;
Arre[top].next:=Arrmap[f];
Arrmap[f]:=top;
end;
procedure Linit;//初始化
var
vi,u,v:longint;
begin
fillchar(map,sizeof(map),false);
fillchar(Arrmap,sizeof(Arrmap),0);//常数写这么大都还过了——唉看来是我想多了
fillchar(Arre,sizeof(Arre),0);
v:=0; i:=0; n:=0; m:=0; top:=0;
flag:=true;
read(n,m);
for vi:=1 to m do
begin
read(u,v);
map[u,v]:=true;//更新邻接链表与邻接矩阵
ins(u,v);
end;
end;
function BFS(x:longint):boolean;//跑BFS
var
h,t,v:longint;
begin
fillchar(Arr,sizeof(Arr),0);
fillchar(Vis,sizeof(Vis),false);
h:=0;
t:=1;
Arr[1]:=x;
vis[x]:=true;
while h<t do
begin
inc(h);
v:=Arrmap[Arr[h]];
while v<>0 do
begin
if not vis[Arre[v].x] then
begin
inc(t);
Arr[t]:=Arre[v].x;
Vis[Arr[t]]:=true;
if not map[x,Arre[v].x] then exit(false);//如果x可以到达e[v],x，然而邻接矩阵中没有这条边，说明R不具有传递性，弹出false
end;
v:=Arre[v].next;
end;
end;
exit(true);//如果遍历完了没有发现不合法的点，那么弹出true
end;
begin
read(T);//读入多组数据
randomize;
for vt:=1 to T do
begin
Linit;//初始化
vp:=1+random(n);//我以为从1开始枚举会卡数据（也就是最后一个点才出现不合法的状态），所以随机了一下
for i:=vp to n do
begin
if not flag then break;
flag:=BFS(i);
end;
for i:=vp-1 downto 1 do
begin
if not flag then break;//跑BFS判断R是否传递
flag:=BFS(i);
end;
if not flag then writeln('No')
else writeln('Yes');//输出
end;
end.