最小可相交路径覆盖
先预处理可到达的点然后转化为最小不相交路径覆盖
type node=record
point,next:longint;
end; var edge:array[..] of node;
p,cx,cy:array[..] of longint;
v:array[..] of boolean;
a,b:array[..,..] of boolean;
j,len,n,m,x,y,ans,i:longint; procedure add(x,y:longint);
begin
inc(len);
edge[len].point:=y;
edge[len].next:=p[x];
p[x]:=len;
end; function find(x:longint):longint;
var i,y:longint;
begin
i:=p[x];
while i<>- do
begin
y:=edge[i].point;
if not v[y] then
begin
v[y]:=true;
if (cy[y]=-) or (find(cy[y])>) then
begin
cx[x]:=y;
cy[y]:=x;
exit();
end;
end;
i:=edge[i].next;
end;
exit();
end; procedure dfs(x:longint);
var i:longint;
begin
v[x]:=true;
for i:= to n do
if a[x,i] and not v[i] then dfs(i);
end; begin
readln(n,m);
fillchar(p,sizeof(p),);
for i:= to m do
begin
readln(x,y);
a[x,y]:=true;
end;
for i:= to n do
begin
fillchar(v,sizeof(v),false);
dfs(i);
for j:= to n do
if v[j] and (i<>j) then
add(i,j);
end;
fillchar(cx,sizeof(cx),);
fillchar(cy,sizeof(cy),);
for i:= to n do
if cx[i]=- then
begin
fillchar(v,sizeof(v),false);
ans:=ans+find(i);
end;
writeln(n-ans);
end.