题意:找一张图中的最小环

O(n)

思路:强连通分量tarjan即可 注意环中节点数>1

 var head,vet,next,s,b,stack,low,dfn,flag:array[..]of longint;
n,i,ans,tot,id,top,time,x:longint; procedure add(a,b:longint);
begin
inc(tot);
next[tot]:=head[a];
vet[tot]:=b;
head[a]:=tot;
end; function min(x,y:longint):longint;
begin
if x<y then exit(x);
exit(y);
end; procedure dfs(u:longint);
var e,v:longint;
begin
flag[u]:=;
inc(top); stack[top]:=u;
inc(time); dfn[u]:=time; low[u]:=time;
e:=head[u];
while e<> do
begin
v:=vet[e];
if flag[v]= then
begin
dfs(v);
low[u]:=min(low[u],low[v]);
end
else if s[v]= then low[u]:=min(low[u],low[v]);
e:=next[e];
end; if low[u]=dfn[u] then
begin
inc(id); s[u]:=id; inc(b[id]);
while (top>)and(stack[top]<>u) do
begin
s[stack[top]]:=id;
inc(b[id]);
stack[top]:=;
dec(top);
end;
stack[top]:=;
dec(top);
end;
end; begin
//assign(input,'1.in'); reset(input);
//assign(output,'1.out'); rewrite(output);
readln(n);
for i:= to n do
begin
read(x);
add(i,x);
end;
for i:= to n do
if flag[i]= then dfs(i);
ans:=n;
for i:= to id do
if (b[i]>)and(b[i]<ans) then ans:=b[i];
if n= then writeln()
else writeln(ans);
//close(input);
//close(output);
end.

最新文章

  1. Displaying Data in a Chart with ASP.NET Web Pages (Razor)
  2. Azure开发者任务之六:使用WCF Service Web Role
  3. HDU 5019 Revenge of GCD(数学)
  4. Oracle 动态视图1 V$LOCK
  5. uva11426 GCD Extreme(II)
  6. android在Canvas使用drawBitmap画一幅画
  7. mysql grant授权
  8. 常用Map实现类对比
  9. 什么是shell? bash和shell有什么关系?
  10. Workbook导出excel封装的工具类
  11. PHP会员找回密码功能实现实例介绍
  12. web app、hybrid app和native app区别
  13. SE-Net要点
  14. 计算字符串最后一个单词的长度,单词以空格隔开。 java算法
  15. vmware导出为ovf
  16. 【转】JavaScript代码性能优化总结
  17. [翻译] UIGlossyButton
  18. php中的static
  19. CS20Chapter2
  20. 推荐系统第4周--- 基于频繁模式的推荐系统和关联规则挖掘Apriori算法

热门文章

  1. Bootstrap标签页(Tab)插件
  2. IDEA设置每次打开重新选择项目
  3. 源自http://www.cnblogs.com/sciencefans/p/4394861.html
  4. NOIP模拟赛 机器人
  5. NOIP模拟赛 准考证号
  6. Intel Code Challenge Elimination Round (Div.1 + Div.2, combined)
  7. 【php】命名空间的影响
  8. Python学习笔记:re模块(正则表达式)
  9. Windows Bash on Ubuntu
  10. PHP中文网 学习阶段规划