强连通分量

强连通分量内 两两点之间可互达。

首席算法： Tarjan

Tarjan 专门用来做这类问题。

dfn[] 数组：遍历的 dfs序

low[] 数组：所能到达的最小的节点编号

stk[] 数组：存点的栈，用来维护同一个联通分量，标记。

vis[] 数组：是否在栈内。

id[] 数组：属于哪个连通分量

1：遍历所有相连的节点，更新 low 数组。

2：如果是连通分量的头（dfn[x]==low[x]）

则开始边退栈边处理同一联通块的信息。

3：最后开始根据不同的题目采取相应的处理方法（和AC自动机一样，前面都是套路、预处理，最后一步才是灵活的）。

例题：

LOJ网络协议

代码：

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int N=10005;
 4 int n,nxt[N],to[N],hea[N],tot1=0,tot2=0,tot=0;
 5 int dfn[N],low[N],id[N],tim,num=0,stk[N],top=0,ans=0;
 6 bool vis[N],rd[N],cd[N];
 7 inline void add(int x,int y)
 8 {
 9     to[++tot]=y; nxt[tot]=hea[x]; hea[x]=tot; 
10 }
11 inline void tarjan(int x)
12 {
13     dfn[x]=low[x]=++tim;
14     vis[x]=1; stk[++top]=x;
15     for (int i=hea[x]; i; i=nxt[i])
16     {
17         int y=to[i];
18         if (!dfn[y])
19         {
20             tarjan(y); low[x]=min(low[x],low[y]);
21         }
22         else if (vis[y])
23         {
24             low[x]=min(low[x],dfn[y]);
25         }
26     }
27     if (dfn[x]==low[x])
28     {
29         vis[x]=0; id[x]=++num;
30         while (stk[top]!=x)
31         {
32             id[stk[top]]=num;
33             vis[stk[top--]]=0;
34         }
35         top--;
36     }
37 }
38 int main()
39 {
40     scanf("%d",&n);
41     for (int i=1; i<=n; ++i)
42     {
43         int x;
44         scanf("%d",&x);
45         while (x!=0)
46         {
47             add(i,x);
48             scanf("%d",&x);
49         }
50     }
51     for (int i=1; i<=n; ++i)
52     {
53         if (!dfn[i]) tarjan(i);
54     }
55     int tot=0;
56     for (int i=1; i<=n; ++i)
57       for (int j=hea[i]; j; j=nxt[j])
58       {
59           if (id[i]!=id[to[j]]) cd[id[i]]=1,rd[id[to[j]]]=1;
60       }
61     for (int i=1; i<=num; ++i)
62     {
63       if (!rd[i]) tot1++;
64       if (!cd[i]) tot2++;
65     }
66     tot2=max(tot1,tot2);
67     if (num==1) tot2=0;
68     printf("%d
",tot1);
69     printf("%d
",tot2);
70     return 0;
71 }

View Code

fighting fighting fighting