图论
Tarjan
Tarjan 求强连通分量
在图中找到一个最大的图，使这个图中的每个两点能够互相到达。
用DFS搜，将每一个强连通分量作为搜索树上的子树。
模板
输出图中的每个强连通分量
//DFN［］作为这个点搜索的次序编号（时间戳
//LOW［］作为每个点在这颗树中的，最小的子树的根，每次保证最小，like它的父亲结点的时间戳这种感觉。如果它自己的LOW［］最小，那这个点就应该从新分配，变成这个强连通分量子树的根节点。
//每次找到一个新点，这个点LOW［］＝DFN［］。
struct node {
int v,next;
}edge[1001];
int DFN[1001],LOW[1001];
int sstack[1001],heads[1001],visit[1001],cnt,tot,index;
void add(int x,int y)
{
edge[++cnt].next=heads[x];
edge[cnt].v = y;
heads[x]=cnt;
return ;
}
void tarjan(int x)//代表第几个点在处理。递归的是点。
{
DFN[x]=LOW[x]=++tot;// 新进点的初始化。
sstack[++index]=x;//进站
visit[x]=1;//表示在栈里
for(int i=heads[x];i!=-1;i=edge[i].next)
{
if(!DFN[edge[i].v]) {//如果没访问过
tarjan(edge[i].v);//往下进行延伸，开始递归
LOW[x]=min(LOW[x],LOW[edge[i].v]);//递归出来，比较谁是谁的儿子／父亲，就是树的对应关系，涉及到强连通分量子树最小根的事情。
}
else if(visit[edge[i].v ]){ //如果访问过，并且还在栈里。
LOW[x]=min(LOW[x],DFN[edge[i].v]);//比较谁是谁的儿子／父亲。就是链接对应关系
}
}
if(LOW[x]==DFN[x]) //发现是整个强连通分量子树里的最小根。
{
do{
printf("%d ",sstack[index]);
visit[sstack[index]]=0;
index--;
}while(x!=sstack[index+1]);//出栈，并且输出。
printf("\n");
}
return ;
}
int main()
{
memset(heads,-1,sizeof(heads));
int n,m;
scanf("%d%d",&n,&m);
int x,y;
for(int i=1;i<=m;i++)
{
scanf("%d%d",&x,&y);
add(x,y);
}
for(int i=1;i<=n;i++)
if(!DFN[i]) tarjan(1);//当这个点没有访问过，就从此点开始。防止图没走完
return 0;
}
//vector 实现邻接表
const int N=100005;
vector <ll> g[N];
stack <ll> s;
ll color[N],vis[N],dfn[N],low[N],cnt[N];// dfn[i] i出现的次序 low[i] 点i在这棵树中最小子树的根
ll deep,top,sum,res=0;//deep 节点编号 top 栈中元素数量 sum 强连通分量的数目
void tarjan(int v){
dfn[v] = low[v] = ++deep;
vis[v]=1;
s.push(v);
for(unsigned i=0;i<g[v].size();i++){
ll id = g[v][i];
if(!dfn[id]){
tarjan(id);
low[v]=min(low[v],dfn[id]);
}
else{
if(vis[id]){
low[v]=min(low[v],dfn[id]);
}
}
}
if(low[v] == dfn[v]){//自己和子节点形成了强连通分量或者自己只有一个人
color[v]= ++sum;
vis[v]=0;
while(s.top()!=v){
color[s.top()]=sum;
vis[s.top()]=1;
s.pop();
}
cout<<endl;
}
}
int main(){
int n,m;
n=read();m=read();
for(int i=1;i<=m;i++){
g[read()].push_back(read());
}
return 0;
}
Tarjan缩点
原理：强连通分量对于一些贡献有传导性
对于一个有向环，可以缩成一个点。
引入问题
一个有向图，有n个点以及m条边，我们至少应该添加几条边才能使整个图变成强连通图。或者是一个无向图至少添加几条边变成连通图。
思路
我们计算入度为零的点数为a，出度为零的点数为b，那么我们至少需要添加的边数为max(a,b)，如果只有一个点的话，我们不需要添加任何边。
那么我们怎么把一个图转换为DAG呢，因为上面给出的图可能存在环，那么我们就会想到把已经组成全连通的子图转换成一个点来看，那么我们最终的图就不会包含环了。
我们使用Tarjan算法求解出强连通分量之后，我们上面使用了一个color数组将同一个连通分量的点分配相同的数值，然后我们再次遍历一遍所有的边，如果边的两侧u->v不属于同一颜色，那么u对应颜色将会有一条边连向v对应的颜色。在此基础上我们可以计算缩点之后的出入度，得到max(a,b)或者其他一些信息。
实现
#define MAX 10005
#define ll long long
vector<ll> g[MAX];
ll color[MAX], vis[MAX], stack[MAX], dfn[MAX], low[MAX], cnt[MAX], num[MAX];
ll ind[MAX], outd[MAX];//每个点的出度入度
//deep:节点编号 top：栈顶 sum：强连通分量数目
ll deep, top, sum, res = 0;
void tanjan(ll v) {
dfn[v] = ++deep;
low[v] = deep; //(1)初始化dfn数组，同时将low设置为相同值
vis[v] = 1;
stack[++top] = v;//(2)入栈，作为栈顶元素，同时更新vis数组
for (unsigned i = 0; i < g[v].size(); i++) {//(3)遍历所有可能到达的点
ll id = g[v][i];
if (!dfn[id]) {//如果这个点从没访问过，则先放问它，再用它更新low[v]的值
tanjan(id);
low[v] = min(low[v], low[id]); //他的儿子如果能连到更小的祖先节点，显然他也可以
}
else {
if (vis[id]) {//不在栈中的点，要么没有访问，要么不能到达id，所以只需要判断栈中的
low[v] = min(low[v], low[id]);
}
}
}
if (low[v] == dfn[v]) {//(4)自己和子节点形成了强连通分量，或者只有自己孤身一人
color[v] = ++sum; num[sum]++; //num统计该颜色有多少点
vis[v] = 0;
while (stack[top] != v) {//将从v开始所有的点取出
color[stack[top]] = sum;//给予同一颜色
vis[stack[top--]] = 0;//出栈要顺便修改vis
num[sum]++;
}
top--;
}
}
int main(){
for (int i = 1; i <= N; i++) {
for (unsigned k = 0; k < g[i].size(); k++) {
ll v = g[i][k];
if (color[v] != color[i]) {//二者分属于不同的联通集
outd[color[i]] += 1; //以颜色作为点，更新相应点的出度
}
}
}
}
Tarjan割点
割点定义：对于一个无向图，如果这个顶点集合以及集合中相关联的边，图的联通分量增多，这个点为割点。
对于根节点，如果子树数量>=2 就是割点（子树互不相连，而且不连向祖先）
对于非根借点 维护数组dfn和low，对于边（u,v),如果low[v]>=dfn[u] u就是割点
解释
low[v]>=dfn[u] 意味着v不能回到u前面 u的儿子可以不通过u访问到u的祖先，那么去掉u后，不影响连通性，那么u就不是割点。反之如果u如果存在儿子节点，必须要通过u链接到u的祖先，那么去掉u，连通性增加，u就是割点。
注意事项！！！
对于tarjan 可以将更新语句改为 low[u]=min(low[u],dfn[v]);
对于割点 这一句就不可以
在求强连通分量中，如果v已经在栈里，那么u,v一定在同一个强连通给分量中，所有Low[u]=low[v]是必然，提前更新也不会有问题。
但是，在求割点过程中，low不能追溯到最早祖先，因为这是一个无向图。应该是最早能绕到的割点。如果把dfn[v]改掉就会翻过头。
void tarjan(ll u, ll r) {// v:当前点 r：本次搜索树的root
dfn[u] = low[u] = ++deep;
ll child = 0;
for (unsigned i = 0; i < g[u].size(); i++) {
ll v = g[u][i];
if (!dfn[v]) {
tarjan(v, r);
low[u] = min(low[u], low[v]);
if (low[v] >= dfn[u] && u != r)cut[u] = 1;//不是根而且他的孩子无法跨越他回到祖先
if (r == u)child++; //如果是搜索树的根，统计孩子数目
}
low[u] = min(low[u], dfn[v]);//已经搜索过了
}
if (child >= 2 && u == r)cut[r] = 1; //是根节点且子树>=2
}
学习博客来源：https://blog.csdn.net/csyifanZhang/article/details/105370924?ops_request_misc=%7B%22request%5Fid%22%3A%22160488705219724836759948%22%2C%22scm%22%3A%2220140713.130102334..%22%7D&request_id=160488705219724836759948&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2alltop_click~default-1-105370924.pc_first_rank_v2_rank_v28p&utm_term=Tarjan&spm=1018.2118.3001.4449