tarjan强连通分量模板（pascal）

友好城市

【问题描述】
小 w 生活在美丽的 Z 国。 Z 国是一个有 n 个城市的大国，城市之间有 m 条单向公路（连接城市 i、 j 的公路只能从 i 连到 j）。城市 i、 j 是友好城市当且仅当从城市 i 能到达城市 j 并且从城市 j 能到达城市 i。如果 k 个城市两两互为友好城市，那么我们称这 k 个城市是友好城市群， k 为友好城市群的大小。

现在小 w 想知道友好城市群的大小最大为多少，你能告诉他吗？

【输入格式】
第一行包含两个整数 n 和 m。
接下来 m 行，每行两个整数 i 和 j，表示有从城市 i 到城市 j 的一条单向公路。

【输出格式】
共一行一个整数表示答案。

【输入输出样例】
输入：
10 12
3 7
1 2
4 5
7 10
10 8
6 8
2 1
3 8
10 3
6 8
7 3
4 1

输出：
3

【数据范围】
对于 30%的数据， n,m<=100
对于 80%的数据， n<=1000,m<=100000
对于 100%的数据， n,m<=100000

裸的tarjan强连通分量题，只是为了打个tarjan板子。（然而我也不是很懂tarjan算法的原理）

 program friend(input,output);

 type

   etype=record

      t,next:longint;

   end;

 var

   e:array[..]of etype;

   a,dfn,low,q:array[..]of longint;

   inq:array[..]of boolean;

   n,m,i,x,y,cnt,top,ans:longint;

 procedure add(x,y:longint);

 begin

    inc(cnt);e[cnt].t:=y;e[cnt].next:=a[x];a[x]:=cnt;

 end;

 procedure tarjan(k:longint);

 var

   i:longint;

 begin

    inc(cnt);dfn[k]:=cnt;low[k]:=cnt;

    inc(top);q[top]:=k;inq[k]:=true;

    i:=a[k];

    while i<> do

       begin

          if dfn[e[i].t]= then begin tarjan(e[i].t);if low[e[i].t]<low[k] then low[k]:=low[e[i].t]; end

          else if inq[e[i].t] and (dfn[e[i].t]<low[k]) then low[k]:=dfn[e[i].t];

          i:=e[i].next;

       end;

    if dfn[k]=low[k] then

       begin

          i:=;

          while q[top]<>k do begin inq[q[top]]:=false;dec(top);inc(i); end;

          dec(top);inq[k]:=false;inc(i);

          if i>ans then ans:=i;

       end;

 end;

 begin

    assign(input,'friend.in');assign(output,'friend.out');reset(input);rewrite(output);

    readln(n,m);

    fillchar(a,sizeof(a),);cnt:=;

    for i:= to m do begin readln(x,y);add(x,y); end;

    fillchar(dfn,sizeof(dfn),);

    ans:=;

    fillchar(inq,sizeof(inq),false);

    for i:= to n do if dfn[i]= then begin cnt:=;top:=;tarjan(i); end;

    write(ans);

    close(input);close(output);

 end.

巴特西

tarjan强连通分量模板（pascal）

最新文章

热门文章