强联通分量与模拟链表
                                                          作者：逸水之寒
1. 强连通分量
强连通分量的定义是：在有向图中，u可以到达v，但是v不一定能到达u，如果u,v
到达，则他们就属于一个强连通分量。
求强连通分量最长用的方法就是Kosaraju算法，比较容易理解而且效率很高，本文对强连通分量的求法均采用Kosaraju算法。
其主要思想：首先对原图G进行深搜形成森林（树），然后选择一棵树进行第二次深搜，注意第一次是要判断节点A能不能通向节点B，而第二次要判断的是节点B能不能通向A，能遍历到的就是一个强连通分量。（附录给出伪代码）
Kosaraju算法如果采用了合适的数据结构，它的时间复杂度是O(n)的。相关题目有很多，例如USACO 5.3.3，2009NOIP Senior No.3。下面将以USACO 5.3.3 schlnet 举例说明。
Preblem 1. Network of Schools (USACO 5.3.3 schlnet\IOI96 No.3)
A number of schools are connected to a computer network. Agreements have been developed among those schools: each school maintains a list of schools to which it distributes software (the "receiving schools"). Note that if B is in the distribution list of school A, then A does not necessarily appear in the list of school B.
You are to write a program that computes the minimal number of schools that must receive a copy of the new software in order for the software to reach all schools in the network according to the agreement (Subtask A). As a further task, we want to ensure that by sending the copy of new software to an arbitrary school, this software will reach all schools in the network. To achieve this goal we may have to extend the lists of receivers by new members. Compute the minimal number of extensions that have to be made so that whatever school we send the new software to, it will reach all other schools (Subtask B). One extension means introducing one new member into the list of receivers of one school.
INPUT FORMAT
The first line of the input file contains an integer N: the number of schools in the network (2<=N<=100). The schools are identified by the first N positive integers. Each of the next N lines describes a list of receivers. The line i+1 contains the identifiers of the receivers of school i. Each list ends with a 0. An empty list contains a 0 alone in the line.
SAMPLE INPUT (file schlnet.in)
5
2 4 3 0
4 5 0
0
0
1 0
OUTPUT FORMAT
Your program should write two lines to the output file. The first line should contain one positive integer: the solution of subtask A. The second line should contain the solution of su
btask B.
SAMPLE OUTPUT (file schlnet.out)
1
2
分析：
    本题需要将强连通分量进行缩点，具体做法可以先求出所有的强连通分量，然后重新建立图，将一个强连通分量用一个点在新图中表示出来。子任务A是求出所有需要得到软件的，需要得到软件的另一种理解就可以认为本节点在新构成的图中入度为0。子任务B是要求通过任意一个学校即可让全部学校都收到软件，也就是说题目要求再添加多少条边就可以使整个图成为一个大的强连通分量。我们知道，如果一个图中存在一个节点，他的出度或入度为0，那么整个图一定不是一个强联通分量，那么我们添加边的策略就可以变成添加最少的边，使得不出现入度或出度为0的节点，添加的边数=max(sum(出度为0的点)，sum（入度为0的点）)。此外有一个特殊情况，就是如果整个图原本就是一个强联通，那么第一问应该输出1，第二问应该输出0。（附录给出AC代码）
2. 模拟链表
PASCAL中数组的功能很少，如果使用数组很多时候时间复杂度很高，这个时候链表的作用就显示出来了。如下表：
数组
链表
定位
O(1)
O(N)
添加或删除
O(N)
O(1)
上表说明，如果我们的程序在进行添加或删除元素的时候，链表的时间复杂度是非常低的，而经常有题目需要添加和删除元素，这就是链表的使用范围很广泛。例如Problem1中，n<=100，如果使用数组，由于n很小，O(n^2)甚至O(n^3)程序都能承受，如果简单的修改一下题目，如下题：
Problem 2.  改编
Problem1 中 n<=100000 边m<=100000
这样的题目，如果采用O(n^2)，程序必定TEL，我们必须优化数据结构使得时间复杂度降成O（n）即可。
由于个人比较厌倦PASCAL中的指针链表，故下面程序采用数组模拟链表来实现。
模拟链表方法1：
    先开足够大的数组，这个数组有两个域，一个是data域，一个是next域，data域存放的是数据，next域存放的是下一个数据的标号（这里等于起到了一个指针的作用），下面为参考代码（PASCAL）：
Type node=record
    Data:longint;          //存放数据
    Next:longint;          //存放下一个数据的标号
A:axn] of longint  //这里要开的足够大，保证不会被溢出
当我们需要一个节点的时候，可以进行如下操作
Inc(top);                  //a[top]就是你需要的节点
A[top].data=你的数据
A[pre].next=top          //需要修改top上一个连接的next域，表示连接到了top
这样的链表虽然写起来简单，也非常好理解，但是却有一个致命的弱点，链表只能表示A节点连接到了B，但是如果我们要统计B节点的入度，就必须要耗费每次查询O(n)的代价，显然这个时候上面的数据结构不够用了，我们需要扩展这个数据结构。这个时候我们可以再开一个数组B（有两个域data,next），同样也需要一个指向B数组的指针( top)，但是这个时候我们并不知道这个链表的尾在什么地方，所以我们必须再添加一个数组en用来表示这个链表的尾，以后添加的时候，只需要查看en数组即可。（附录给出o(n)的problem1的程序）
自己的实践证明，如果只统计出度的话，这种方法的代码复杂度还能承受，但是如果需要同时统计入度，代码就会变得很累赘。建议如果同时统计入度和出度的时候，不要使用这种模拟链表的方法。
模拟链表方法2：
这个方法在OI界广泛流传，代码如下
last[点]=边  记录和这个点相连的最后一条边
pre[边]=边    记录和同一点相连的上一条边
other[边]=点  记录的这条边的另一个点
如果需要建图，则：
readln(x,y);                  //表示x可以到y
inc(e);                      //边数加一
pre[e]:=last[x];              //e这条边的上一条边是x这个点的最后一条边
last[x]:=e;                  //x的最后一条边是现在的e数组和链表
other[e]:=y;                //e的另一条边是y
如果需要知道x这个点能连接的全部节点，则：
P:=last[x];
While p<>0 do
Begin
  处理Other[p]
  p:=pre[p];
End;
如果您采用了模拟链表方法1，如果你要统计入度的点，写起来会很复杂，但是如果您使用模拟链表方法2，统计入度的点只需要在新建立三个数组pre,other,last，原先的x连接y变成了y连接x即可。（附录给出模拟链表方法2的程序）
附录：
(1) 强连通分量伪代码
procedure kosaraju;
var i:longint;
procedure forthdfs(u:longint);
var i:longint;
begin
  v[u]:=true;
  for i:=1 to n do
    if (not v[i]) and g[u,i] then
      forthdfs(i);
  inc(time);
  order[time]:=u;

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。