强连通分量（scc）:Tarjan算法

dfn[u]表示节点u被遍历到的时间，low[u]表示节点u所能回到的最早被遍历到的节点的时间。初次遍历到节点u时，将dfn[u]、low[u]都初始化为u被遍历时的时间，并将u压入栈内

遍历到节点u时,往下遍历节点v的两种情况:

• 1.v被遍历过，且当前就在栈内:此时意味着v是u的一个祖先，通过min(low[u],dfn[v])更新u所能到的更早的节点
• 2.v尚未被遍历:直接往下递归，回溯时用min(low[u],low[v])更新u所能到的更早的节点

遍历完u所能到达的节点后，如果low[u]还是等于dfn[u],说明u无法到达更早的节点，它就是当前强连通分量的根节点。依次弹出栈内节点直到u，则弹出的节点（包括u）属于同一个强连通分量

void Tarjan(int u){
	dfn[u]=low[u]=++t;
	s.push(u);
	ins[u]=true;
	for(int i=0;i<g[u].size();i++){
		int v=g[u][i];
		if(!dfn[v]){
			Tarjan(v);
			low[u]=min(low[u],low[v]);
		}
		else if(ins[v]){
			low[u]=min(low[u],dfn[v]);
		}
	}
	if(dfn[u]==low[u]){
		int v;
		cnt++;
		do{
			v=s.top();
			s.pop();
			ins[v]=false;
			scc[v]=cnt;
		}while(u!=v);
	}
}

最近公共祖先(lca):倍增算法

基本思路：对于求u,v的lca，首先将u与v的深度对齐，再向上搜索，直到找到同一个节点，而那个节点就是它们的lca

倍增优化:令fa[u][j]表示节点u向上的第2^j个祖先。由于任何一个整数都能被拆分为几个不同的2的幂次方的和，即从二进制转为十进制的过程，所以求节点u往上的第d个祖先，可以从u往上进行几次2的幂次方的跳跃，使最终的跳跃节点个数刚好为d

之后，我们将该方法套用到基本思路上。要对齐深度，只需让更深的点往上跳它们的深度差个点即可。而对于寻找第一个共同节点，我们要从能跳跃的最大的距离开始跳，依次减小可跳跃距离，在二者跳跃到的点不是同一个点时，我们才让它们向上跳。跳跃结束后，它们所在的节点的父节点即为它们的lca

//初始化fa和d深度 
void dfs(int u,int f){
	fa[u][0]=f;
	//往上第2^j个节点，即为第2^(j-1)个节点往上的第2^(j-1)个节点，因为2^(j-1)*2=2^j 
	for(int i=1;i<=log2(n);i++){
		fa[u][i]=fa[fa[u][i-1]][i-1];
	}
	for(int i=0;i<g[u].size();i++){
		int v=g[u][i];
		if(v==fa[u][0])	continue;
		depth[v]=depth[u]+1;
		fa[v][0]=u;
		dfs(v,u);
	}
}
//从u往上跳d个节点 
int up(int u,int d){
	for(int i=0;d;i++){
		if((d&1))	u=fa[u][i];
		d=(d>>1);
	}
	return u;
}
int lca(int u,int v){
	if(depth[u]>depth[v])	swap(u,v);
	int d=depth[v]-depth[u];    
	v=up(v,d);
	if(u==v)	return u;
	for(int i=log2(n);i>=0;i--){
		if(fa[u][0]!=fa[v][0]){
			u=fa[u][i];
			v=fa[v][i];
		}
	}
	return fa[u][0];
}