【NOIP2015】信息传递(强连通分量)
2024-08-24 06:35:58
题意:找一张图中的最小环
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.
最新文章
- Displaying Data in a Chart with ASP.NET Web Pages (Razor)
- Azure开发者任务之六:使用WCF Service Web Role
- HDU 5019 Revenge of GCD(数学)
- Oracle 动态视图1 V$LOCK
- uva11426 GCD Extreme(II)
- android在Canvas使用drawBitmap画一幅画
- mysql grant授权
- 常用Map实现类对比
- 什么是shell? bash和shell有什么关系?
- Workbook导出excel封装的工具类
- PHP会员找回密码功能实现实例介绍
- web app、hybrid app和native app区别
- SE-Net要点
- 计算字符串最后一个单词的长度,单词以空格隔开。 java算法
- vmware导出为ovf
- 【转】JavaScript代码性能优化总结
- [翻译] UIGlossyButton
- php中的static
- CS20Chapter2
- 推荐系统第4周--- 基于频繁模式的推荐系统和关联规则挖掘Apriori算法
热门文章
- Bootstrap标签页(Tab)插件
- IDEA设置每次打开重新选择项目
- 源自http://www.cnblogs.com/sciencefans/p/4394861.html
- NOIP模拟赛 机器人
- NOIP模拟赛 准考证号
- Intel Code Challenge Elimination Round (Div.1 + Div.2, combined)
- 【php】命名空间的影响
- Python学习笔记:re模块(正则表达式)
- Windows Bash on Ubuntu
- PHP中文网 学习阶段规划