题目大意:求带重边的连通图至少加几条边变成双连通图
POJ 3352
+重边
用邻接矩阵的表示无压力
Program P3177;
const
maxn=1000;
maxm=1000;
var
n,m,i,j,x,y:longint;
b:array[1..maxn,1..maxn] of boolean;
indegree,c,a,low:array[1..maxn] of longint;
time:longint;
function min(a,b:longint):longint;
begin
if a<b then exit(a) else exit(b);
end;
function max(a,b:longint):longint;
begin
if a>b then exit(a) else exit(b);
end;
procedure tarjan(k,father:longint);
var
i,j:longint;
begin
inc(time);
a[k]:=time;
low[k]:=time;
c[k]:=1;
for i:=1 to n do
begin
if (b[i,k]) and (i<>father) and (a[i]<a[k]) then
begin
if c[i]=0 then
begin
tarjan(i,k);
low[k]:=min(low[k],low[i]);
end;
if (c[i]=1) and (i<>father) then
begin
low[k]:=min(low[k],a[i]);
end;
end;
end;
c[k]:=2;
end;
procedure main;
var
i,j,tot:longint;
begin
fillchar(a,sizeof(a),0);
fillchar(low,sizeof(low),0);
fillchar(c,sizeof(c),0);
fillchar(indegree,sizeof(indegree),0);
time:=0;
tarjan(1,0);
for i:=1 to n do
for j:=i+1 to n do
if (low[i]<>low[j]) and (b[i,j]) then
begin
inc(indegree[low[i]]);
inc(indegree[low[j]]);
end;
tot:=0;
for i:=1 to n do if indegree[i]=1 then inc(tot);
writeln((tot+1) div 2);
end;
begin
fillchar(b,sizeof(b),false);
read(n,m);
for i:=1 to m do
begin
read(x,y);
b[x,y]:=true;
b[y,x]:=true;
end;
main;
end.
分享到:
相关推荐
POJ3177-Redundant Paths 【Tarjan-边双连通分量-缩点】 解题报告+AC代码+测试数据 http://hi.csdn.net/!s/GPAY6Z 附:我所有的POJ解题报告链接 . http://blog.csdn.net/lyy289065406/article/details/6642573
POJ3352-Road Construction 【Tarjan-边双连通分量-缩点】 解题报告+AC代码 http://hi.csdn.net/!s/0T8UO5 附:我所有的POJ解题报告链接 . http://blog.csdn.net/lyy289065406/article/details/6642573
POJ2186-Popular Cows ...【Tarjan+极大强连通分量+缩点】 解题报告+AC代码 http://hi.csdn.net/!s/BGDH68 附:我所有的POJ解题报告链接 . http://blog.csdn.net/lyy289065406/article/details/6642573
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
北大POJ1159-Palindrome 解题报告+AC代码
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
北大POJ初级-图算法 解题报告+AC代码
POJ第1861题源码 POJ第1861题源码 POJ第1861题源码
poj分类poj分类poj分类poj分类
poj 3414解题报告poj 3414解题报告poj 3414解题报告poj 3414解题报告
poj 1012解题报告poj 1012解题报告poj 1012解题报告poj 1012解题报告
poj 2329解题报告poj 2329解题报告poj 2329解题报告poj 2329解题报告
poj 1659解题报告poj 1659解题报告poj 1659解题报告poj 1659解题报告
北大POJ3295-Tautology 解题报告+AC代码
C语言 poj npu 西工大 C语言Poj答案全完整打包,给有需要的朋友
poj 百练 题目分类 poj 百练 题目分类
POJ1083的代码,POJ1083的代码,POJ1083的代码
POJ1503解答 POJ1503解答,正确答案(已通过POJ)
POJ1048,加强版的约瑟夫问题 难度中等
北大POJ2002-Squares 解题报告+AC代码