tarjan算法求图中环（强连通分量）_tarjan寻找图中的环

tarjan

介绍

• tarjan 百度百科
• 另一个介绍及分析
• 本来还有一个当时看的 byvoid 但不知为何登不上了。。。O__O”…
• 横叉边啥啥的概念
• 为嘛原来能看的都不能看了。。。

代码

（附带解释，图可参照介绍中第二个网址）

program tarjan;
type node=^rec;
    rec=record
     next:node;
     name:longint;
    end;
var stack:array[1..1000] of longint;  {栈}
    can:array[1..1000] of boolean;{栈内标记，true 表示在栈中}
    dfn:array[1..1000] of longint;{DFN搜索序}
    belong:array[1..1000] of longint;{连通分量标志数组}
    low:array[1..1000] of longint;{low追溯最初位置}
    vertex:array[1..1000] of node;{顶点表}
    top,belongx,n:longint;{top栈顶指针，belongx连通分量标志}
    step,x,y,m,i:longint;

procedure insert(x,y:longint);  {建图，邻接表}
var p:node;
begin
 new(p);
 p^.next:=vertex[x];
 p^.name:=y;
 vertex[x]:=p;
end;

procedure tarjan(i:longint);
var j:longint;
    p:node;
begin
 step:=step+1;
 dfn[i]:=step;
 low[i]:=step;
 can[i]:=true;
 top:=top+1;
 stack[top]:=i;
 p:=vertex[i];
 while p<>nil do
  begin
   j:=p^.name;  
   p:=p^.next;  {取出下一条边}
   if dfn[j]=0
    then
     begin
      tarjan(j);
      if low[j]<low[i]  {i能够找到j，所以j能够回溯到的i肯定能够找到，比较哪个回溯更远}
       then
        low[i]:=low[j];
     end
    else
     begin
      if can[j] and (low[j]<low[i])  {如果j已经在栈中，并且j的回溯比i远，那么就将i的回溯换为j的回溯,如果j不在栈中又DFN[j]<>0那么j必然在以前搜过且退栈，即已在另一个环中且i不在这个环上}
       then
        low[i]:=low[j];
     end;
  end;
   if dfn[i]=low[i]   {如果dfn[i]=low[i]就说明找到一个连通分量，因为既搜索到i,又回溯到i，构成了一个回路}
    then
     begin
      inc(belongx);
      repeat               {弹栈}
       j:=stack[top];
       stack[top]:=0;
       top:=top-1;
       can[j]:=false;
       belong[j]:=belongx;
      until (j=i)
     end;
end;

begin
 assign(input,'D:/input/tarjan.txt');
 reset(input);
 assign(output,'D:/output/tarjan.txt');
 rewrite(output);
 readln(n,m);
 for i:=1 to n do
  begin
   dfn[i]:=0;
   low[i]:=0;
   vertex[i]:=nil;
   can[i]:=false;
  end;
 for i:=1 to m do
  begin
   readln(x,y);
   insert(x,y);
  end;
 top:=0;
 step:=0;
 for i:=1 to n do
  begin
   if dfn[i]=0
    then tarjan(i);
  end;
 for i:=1 to n do
  write(i, ' ');
 writeln;
 for i:=1 to n do
  write(belong[i],' ');
 close(input);
 close(output);
end.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101

大致就是这样了。。。

题目

呃呃，自力更生。
去各大网站找就好了。。。

每日一句

青春是用意志的血滴和拼搏的汗水酿成的琼浆——历久弥香；青春是用不凋的希望和不灭的向往编织的彩虹——绚丽辉煌；青春是用永恒的执著和顽强的韧劲筑起的一道铜墙铁壁——固若金汤。

点点滴滴汇成往事，往事又如泉水般涌入脑海。。。

那年夏天 - 许飞

赶脚每日一句都快成我的日记了。。呃呃，无视这句话吧。。。