强连通分量的专题早在一个月前就AK了，虽然这是个很基础的算法，在图论中的地位不容小觑，和最短路一样十分重要；
强连通分量和强连通图的概念想必是不用多说了
在有向图G中，如果两点互相可达，则称这两个点强连通，如果G中任意两点互相可达，则称G是强连通图。
非强连通有向图的极大强连通子图，称为强连通分量。
Kosaraju算法
为什么先讲这个呢，因为这个算法从理解上来说要好懂一些；
首先我们来看一张图
这张图里有两个强连通分量，分别是(A1,A2,A3)和(B1,B2,B3)
容易想到，如果我们从b开始DFS，那么经过两次DFS可以遍历完全图，并且每次遍历的都是不同的连通分量；但是如果从a开始就不能得到正确的答案，因为只需要一次DFS就能遍历完全图，显然是错误的；
为什么呢，因为如果先访问那些指向了其他分量的分量，DFS一定能进入到其他连通分量中，这是我们不想得到的。
显然，为了找出全部的强连通分量，我们只要保证DFS访问顶点的顺序为B强连通分量中任意一个顶点在A强连通分量全部顶点之前即可。
那么也就是说我们需要找到一个正确的DFS顺序，保证一次调用DFS肯定是在同一个连通分量里面遍历，而不会跑到其他连通分量中。
那么现在的问题转化成了如何确定正确的顶点顺序；
Kosaraju算法的做法是：先将原图取反，然后从任意节点开始DFS逆后序遍历，得到的顶点顺序就是答案；那么什么是逆后序呢？
逆后序即DFS递归调用返回之前，将该顶点压入栈中得到的序列，通俗的讲就是拓扑序。
那么为什么这样的顶点序就是正确的呢？
由于我们先对原图取了反，那么对于上面那幅图来说DFS只有两种可能，就是从A中某个点开始或者B、中某个点开始；
如果从A中开始DFS，那么需要两次DFS，第一次A1,A2,A3入栈，第二次B1,B2,B3入栈，保证了B中有点在A之前；
如果从B中开始DFS，需要一次DFS即可遍历全图，假设从B2开始遍历，那么除了B2之外的其他点先入栈，最后才是B2点，这样也保证了B中有点在A之前；
显然当连通分量个数大于2时结论也成立；
现在有了正确的DFS顶点顺序，再进行一次DFS就能找到所有强连通分量了；
Kosaraju模版
//Kosaraju
const int maxn =1e5, maxm=2e5;
struct node{
int to,next;
}g[maxm],g2[maxm]; //逆图,原图
int dfn[maxn],head1[maxn],head2[maxn],belong[maxn],num[maxn];
//dfn时间戳
//belg记录每个点属于哪个连通分量
//num记录强连通分量点的个数
bool vis[maxn];
int cnt,cnt1,scc,tot1,tot2;
void init(){
tot1=tot2=0;
memset(head1,-1,sizeof(head1));
memset(head2,-1,sizeof(head2));
memset(num,0,sizeof(num));
}
void addedge(int u,int v){
g2[tot2]={v,head2[u]}; head2[u]=tot2++;
g[tot1]={u,head1[v]}; head1[v]=tot1++;
}
void dfs1(int u){//求逆后序
vis[u]=1;
for(int k=head2[u];~k;k=g2[k].next)
if(!vis[g2[k].to]) dfs1(g2[k].to);
dfn[++cnt1]=u;
}
void dfs2(int u){
vis[u]=1; cnt++;
belong[u]=scc;
for(int k=head1[u];~k;k=g[k].next)
if(!vis[g[k].to]) dfs2(g[k].to);
}
void Kosaraju(int n){
memset(dfn,0,sizeof(dfn));
memset(vis,0,sizeof(vis));
cnt1=scc=0;
for(int i=1;i<=n;i++)
if(!vis[i]) dfs1(i);
memset(vis,0,sizeof(vis));
for(int i=cnt1;i>0;i--)
if(!vis[dfn[i]]){
cnt=0;
++scc;
dfs2(dfn[i]);
num[scc] = cnt;
}
}
Tarjan算法
总的来说， Tarjan算法是基于一个观察，即：同处于一个SCC中的结点必然构成DFS树的一棵子树。 我们要找SCC，就得找到它在DFS树上的根。
Tarjan算法有两个重要的数组：DFN[]和LOW[]，理解了这两个数组，Tarjan也就理解的差不多了；
DFN[]：每个点搜索的次序编号（时间戳），简单来说就是第几个被搜索到的。显然每个点的时间戳都不一样，并且一旦某个点被DFS到后，这个时间戳就不再改变；
LOW[]：该点所在子树中，仍在栈中的最小时间戳；也即这个点所能到达的最小的时间戳；
初始时DFN[] = LOW[]= ++index
我们在DFS时，对于每个点，寻找与其相连的点，判断这些点是否已经被搜索过，若没有，则进行搜索。若该点已经入栈，说明形成了环，则维护low[u]=min(low[u]，low[v])
当dfn[u]=low[u]时，以u为根的搜索子树上所有节点是一个强连通分量；此时u也被称为关键点；
显然，关键点能够遍历其属强连通分量的起始点，而且这样的起始点一定只有一个，所以只要发现了一个这样的关键起始点，那么就一定发现了一个强连通分量。而且这个节点没有(属于其他强连通分量的点)能够有一条有向路径连到这个节点来：如果这样的点存在，那么这些点应该属于同一个强连通分量。
Tarjan模版
int n,m;
int sz, dfn[maxn],low[maxn],vis[maxn],belong[maxn];
int scc;//强连通分量个数
stack<int> sta;
void init(){
rep(i,0,n) vis[i]=0,head[i]=-1,dfn[i]=0;
while(!sta.empty()) sta.pop();
scc = cnt = sz = 0;
}
void tarjan(int u){
dfn[u]=low[u]=++sz; vis[u]=1; sta.push(u);
for(int i = head[u]; ~i; i = g[i].next) {
int v = g[i].to;
if(!dfn[v]){
tarjan(v);
low[u] = min(low[u], low[v]);
}else if(vis[v] && low[u] > dfn[v]) low[u]=dfn[v];
}
if(low[u]==dfn[u]) {
scc++;
while(1){
int id = sta.top(); sta.pop();
vis[id] = 0;
belong[id]=scc;
if(id == u) break;
}
}
}
好啦，强连通分量介绍完了，那么为什么说它重要呢？由于在许多图论题中，只要涉及到DFS基本都要处理环的部分，有时这是一个很复杂的工作，但是如果我们采用强连通分量缩点，就可以把原图变成一个DAG，即有向无环图，这样在解决某些问题时就方便了很多。
比如对于这道题：
给定一个有向图，每个点i有点权w(i)，请对于每个点i，找到i能到达的点中点权的最大值（包括i点）。
对于无环图显然一次记忆化搜索就可以得到答案 ans[u]=max(w[u],ans[v])，但是题目中没有说无环，那么我们就可以先缩点建立新图，对于缩完的每个新点，他们的权值显然是这个连通分量中所有点权中最大的那个；
缩点代码
void work(){ //缩点
rep(i,1,n) if(!dfn[i]) tarjan(i);
int de[maxn]={0,};//入度
rep(i,1,n)
for(int j=head[i];j!=-1;j=g[j].next){
int v=g[j].to;
if(belong[i]!=belong[v]) addedge(belong[i],belong[v]),de[belong[v]]++;
}
rep(i,1,scc) if(!de[i]) {//...}
}
