1.求解强连通分量

1.1定义：

有向图强连通分量：在有向图G中，如果两个顶点vi,vj间（vi>vj）有一条从vi到vj的有向路径，同时还有一条从vj到vi的有向路径，则称两个顶点强连通(strongly connected)。如果有向图G的每两个顶点都强连通，称G是一个强连通图。有向图的极大强连通子图，称为强连通分量。

1.2求法

通过肉眼可以很直观地看出1-2-3是一组强连通分量，但很遗憾，机器并没有眼睛，所以该怎么判断强连通分量呢？

上面那张图，我们对它进行dfs遍历。可以注意到红边非常特别，因为如果按照遍历时间来分类的话，其他边都指向在自己之后被遍历到的点，而红边指向的则是比自己先被遍历到的点。

从一个点出发，一直向下遍历，然后忽得找到一个点，那个点竟然有条指回这一个点的边！

那么想必这个点能够从自身出发再回到自身

想必这个点和其他向下遍历的该路径上的所有点构成了一个环，

想必这个环上的所有点都是强联通的。

但是我们想要知道的是这个图的强联通分量。

只需要知道这个点u下面的所有子节点有没有连着u的祖先就行了。

可是我们怎么知道这个点u它下面的所有子节点一定是都与他强联通的呢？

这似乎是不对的，这个点u之下的所有点不一定都强联通

那么怎么在退回到这个点的时候，知道所有和这个点u构成强连通分量的点呢？

开个栈记录就行了

具体实现还要看代码。

1.3代码

我们需要几个数组来完成Tarjan算法

1. dfn 数组表示该结点是第几个遍历到的
2. low数组表示该结点，及其它的子结点，能够到达的所有结点中dfn最小的点，也就是最早遍历到的点
3. stack 即上文所说的栈，表示当前所有可能存在于当前强联通分量点的集合。即如果这里面的某些点已经组成了强连通分量，就把这所有的点弹出。
4. vis 数组表示这个点会否在栈里

接下来我们开始遍历每一个点。

遍历到u时，首先初始化u的dfn和low都为当前节点的遍历序号。

然后将u打入栈中，去遍历它的每个子节点，如果它的子节点没有被访问到，就访问，如果访问到了，就不去访问。u所有子节点的最小low值，即为u的low值

在u及其子节点访问完后，它的low值再也不会变化。

如果做完了上面这一切，我们如何判断u及其一些子节点能否变成一个强联通分量。

注意：这里，如果u的子节点已经自己成为了一个强联通分量，它已经出栈

试想一下，如果这时候u的dfn和low值相同，会怎么样？

两种情况：

1. u的子节点（还在栈中的）全部能回到u，且回不到比u更早遍历的节点
2. u的所有子节点都回不到u，这时u自己一个节点是一个强联通分量。

如果是第1种情况，那么比u后遍历到的节点，在栈中的，一定可以和u构成一个强连通分量。

如果是第二种情况，代表着u的所有子节点都无法和u构成强连通分量，也就不在栈中。

所以，如果出现这种情况（u的dfn和low值相同），那么在栈中的u上面的节点（不是都说栈顶吗，我们假设这个栈是站立的）和u一定能构成强连通分量。

否则，u的low值一定比dfn值小，这时一定会存在一个u的祖先节点，或是另一分支的节点。

例题：https://www.luogu.com.cn/problem/P3387

代码：

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<sstream>
#include<queue>
#include<map>
#include<vector>
#include<set>
#include<deque>
#include<cstdlib>
#include<ctime>
#define dd double
#define ll long long
#define ld long double
#define ull unsigned long long
#define N 20000
#define M 100100
using namespace std;

inline int Max(int a,int b){
	return a>b?a:b;
}

inline int Min(int a,int b){
	return a>b?b:a;
}

struct edge{
	int to,next;
	inline void intt(int to_,int next_){
		to=to_;next=next_;
	}
};
edge li[M],li2[M];
int head[N],tail,head2[N],tail2;

inline void add(int from,int to){
	li[++tail].intt(to,head[from]);
	head[from]=tail;
}

inline void add2(int from,int to){
	li2[++tail2].intt(to,head2[from]);
	head2[from]=tail2;
}

int dfn[N],low[N],stack[N],top,deep,co_num,co[N];
bool vis[N];

inline void tarjan(int u){
	dfn[u]=++deep;low[u]=deep;stack[++top]=u;vis[u]=1;
	for(int x=head[u];x;x=li[x].next){
		int to=li[x].to;
		if(!dfn[to]){
			tarjan(to);
			low[u]=Min(low[u],low[to]);
		}
		else if(vis[to]) low[u]=Min(low[u],low[to]);
	}
	if(low[u]==dfn[u]){
		co[u]=++co_num;
		vis[u]=0;
		while(stack[top]!=u){
			co[stack[top]]=co_num;
			vis[stack[top]]=0;
			top--;
		}
		top--;
	}
}

int n,m,a[N],p[N],f[N];

inline void dfs1(int u){
	vis[u]=1;
	for(int x=head[u];x;x=li[x].next){
		int to=li[x].to;
		if(co[to]!=co[u]) add2(co[u],co[to]);
		if(!vis[to]) dfs1(to);
	}
}

inline int dfs2(int u){
	
	if(f[u]) return f[u];
	for(int x=head2[u];x;x=li2[x].next){
		int to=li2[x].to;
		f[u]=Max(f[u],dfs2(to));
	}
	f[u]+=p[u];
	return f[u];
}

int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	for(int i=1;i<=m;i++){
		int from,to;
		scanf("%d%d",&from,&to);
		add(from,to);
	}
	for(int i=1;i<=n;i++) if(!dfn[i]) tarjan(i);
	memset(vis,0,sizeof(vis));
	for(int i=1;i<=n;i++) if(!vis[i]) dfs1(i);
	for(int i=1;i<=n;i++) p[co[i]]+=a[i];
	memset(vis,0,sizeof(vis));
	for(int i=1;i<=co_num;i++) if(!f[i]) f[i]=dfs2(i);
	int maxx=-1;
	for(int i=1;i<=co_num;i++) maxx=Max(maxx,f[i]);
	printf("%d",maxx);
	return 0;
}

这个题博主做麻烦了。实际上可以在原来的路径上直接改图，但是出题人没有像z*c一样爱卡空间和时间。所以能过。

2.Tarjan求割点

tarjan算法还是可以求割点的。

在一个无向图中，如果有一个顶点集合，删除这个顶点集合以及这个集合中所有顶点相关联的边以后，图的连通分量增多，就称这个点集为割点集合。

简单点说就是你把割点去掉后，这个图就好似被撕成了几个部分一样，各个部分之间不再联通。

还是一样，我们继续用上面的dfn和low数组，但是这里，low数组的定义会有变化

定义如下：最早能绕到的点

因为是无向图，所以不存在祖先。

同时，如果比u晚遍历到的点的low值还比u的dfn小的话（或者等于），那么去掉点u，肯定会多一个联通图。

同时还要注意判断dfs树的根节点，如果根节点儿子数目大于等于2，则根节点也是一个割点。

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<sstream>
#include<queue>
#include<map>
#include<vector>
#include<set>
#include<deque>
#include<cstdlib>
#include<ctime>
#define dd double
#define ll long long
#define ld long double
#define ull unsigned long long
#define N 30010
#define M 200100
using namespace std;

struct edge{
	int to,next;
	inline void intt(int to_,int next_){
		to=to_;next=next_;
	}
};
edge li[M];
int head[N],tail;

inline int Min(int a,int b){
	return a>b?b:a;
}

inline void add(int from,int to){
	li[++tail].intt(to,head[from]);
	head[from]=tail;
}

int dfn[N],low[N],deep;
bool iscut[N];

inline void tarjan(int u,int fa){
	dfn[u]=++deep;low[u]=deep;
	int child=0;
	for(int x=head[u];x;x=li[x].next){
		int to=li[x].to;
		if(!dfn[to]){
			child++;
			tarjan(to,u);
			low[u]=Min(low[u],low[to]);
			if(low[to]>=dfn[u]) iscut[u]=1;
		}
		else low[u]=Min(low[u],dfn[to]);//尤其注意这句话
	}
	if(fa==-1&&child==1) iscut[u]=0;
}

int n,m;

int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++){
		int from,to;
		scanf("%d%d",&from,&to);
		add(from,to);
		add(to,from);
	}
	for(int i=1;i<=n;i++) if(!dfn[i]) tarjan(i,-1);
	int ans=0;
	for(int i=1;i<=n;i++) if(iscut[i]) ans++;
	printf("%d\n",ans);
	for(int i=1;i<=n;i++) if(iscut[i]) printf("%d ",i);
}