笔记
1、出度：以顶点v为起点的弧的数目
入度：顶点v为终点的弧的数目
2、如果在有向图G中，有一条<u，v>有向道路，则v称为u可达的，或者说，从u可达v。
3、强连通图：若有向图G的任意两个顶点都互相可达，则称图 G是强连通图，如果有向图G存在两顶点u和v使得u不能到v，或者v不能到u，则称图G是强非连通图。
4、强连通分量：如果有向图G不是强连通图，他的子图G2是强连通图，点v属于G2，任意包含v的强连通子图也是G2的子图，则称G2是有向图G的极大强连通子图，也称强连通分量。
5、极大强连通子图（强连通分量）解释：一个图的强连通子图，并且加入任何一个不在它的点集中的点都会导致它不再强连通。
6、强连通分量里边的任意两个点，都是互相可达的。
算法解析
1、Tarjan算法，是一个基于Dfs（深搜）的算法，假设我们要先从0号节点开始Dfs，我们发现一次Dfs我门能遍历整个图，而且我们发现，在Dfs的过程中，我们深搜到 了其他强连通分量中，那么我们Dfs之后如何判断哪个和那些节点属于一个强连通分量呢？
之所以用DFS就是因为它将每一个强连通分量作为搜索树上的一个子树。而这个图，就是一个完整的搜索树。
为了使这颗搜索树在遇到强连通分量的节点的时候能顺利进行。每个点都有两个参数。
2、首先引入两个数组
int dfn[]; //点搜索的次序编号 int low[]; //每个点在这颗树中的，最小的子树的根
3、Tarjan算法在搜索过程中把没有Tarjan过的点入栈并将该节点的dfn[i] = low[i] = ++dfs_num（也就是设成他自己），然后以这个节点为树根再进行搜索，当一颗子树搜索完毕时回溯，并在回溯时比较当前节点和目标节点的LOW值，将较小的LOW值赋给当前结点的LOW，这样可以保证每个节点在以其为树根的子树的所有节点中LOW值是最小的。如果回溯时发现当前节点DFN[i]==LOW[i]，就将栈中当前结点以上的节点全部弹栈，这些点就组成了一个强连通分量。还要注意一点是，当目标节点进行过Tarjan但还在栈中，就拿当前节点LOW值与目标节点DFN值比较，把更小的赋给当前结点的LOW。
①对于从没访问过的节点：加入栈中让其DFN[i]=LOW[i]=++dfs_num，让vis[i]=1表示该点入栈了。这类点的标志是!DFN[i]&&!vis[i]。
②对于访问过但不在栈中的节点(!vis[i])直接回溯即可，因为既然该节点访问过了又不在栈中，就必定属于另一个强连通分量。这类点的标志是DFN[i]&&!vis[i]。
②对于访问过且在栈中的节点，比较当前节点LOW值和目标节点DFN值，将较小的赋给当前结点LOW值然后回溯。这类点的标志是DFN[i]&&vis[i]。
算法模板
评测：洛谷：P2863
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
using namespace std;
const int MAXN = 100005;
const int MAXM = 500005;
struct node {
int next,to;
} e[MAXN];
int cnt,num,n,m,dfn[MAXN],low[MAXN],head[MAXN],ans;
int cut[MAXN];
int all;
bool vis[MAXN];
stack< int > s;
void add(int ,int );
void work();
void Tarjan(int );
int main() {
cin >> n >> m;
for(int i = 1;i <= m;++i) {
int from,to;
cin >> from >> to;
add(from,to);
}
work();
return 0;
}
void add(int from,int to) {
e[++cnt].next = head[from];
e[cnt].to = to;
head[from] = cnt;
}
void work() {
for(int i = 1;i <= n;++i)
if(!dfn[i]) Tarjan(i);
for(int i = 1;i <= all;++i) if(cut[i] > 1) ans++;
cout << ans << endl;
}
void Tarjan(int u) {
dfn[u] = low[u] = ++num;
s.push(u);
vis[u] = true;
for(int i = head[u];i;i = e[i].next) {
int v = e[i].to;
if(!dfn[v]) {
Tarjan(v);
low[u] = min(low[u],low[v]);
}
else if(vis[v]) low[u] = min(low[u],dfn[v]);
}
if(dfn[u] == low[u]) {
all++;
while(s.top() != u) {
int k = s.top();
s.pop();
vis[k] = false;
cut[all]++;
}
s.pop();
cut[all]++;
vis[u] = false;
}
}
参考：
https://blog.csdn.net/mengxiang000000/article/details/51672725
https://blog.csdn.net/qq_34374664/article/details/77488976
https://www.cnblogs.com/reddest/p/5932153.html
文章评论