图论

邻接表

struct Graph{
	int fir[N],nex[M],to[M],tot;
	inline void add(int u,int v,int flag=1){
		to[++tot]=v;
		nex[tot]=fir[u];fir[u]=tot;
                if(flag) add(v,u,0);
	}
	inline void clear(){
		std::memset(fir,0,sizeof fir);tot=0;
	}
}G;

tarjan 缩强连通分量

int dfn[N],low[N],dfscnt;
int stack[N],top;
int scc[N],scccnt;
void tarjan(int u){
	dfn[u]=low[u]=++dfscnt;
	stack[top++]=u;
	for(int v,i=G.fir[u];i;i=G.nex[i]){
		v=G.to[i];
		if(!dfn[v]){
			tarjan(v);
			low[u]=std::min(low[u],low[v]);
		}
		else if(!scc[v]) low[u]=std::min(low[u],dfn[v]);
	}
	if(dfn[u]==low[u]){
		scccnt++;
		do{
			scc[stack[--top]]=scccnt;
		}while(stack[top]^u);
	}
}

spfa 找负环

int dis[N],cnt[N];
int left,right,que[N];
inline int spfa(){
	std::memset(dis,0x3f,sizeof dis);std::memset(cnt,0,sizeof cnt);
	right=left=0;que[0]=1;
	dis[1]=0;
	int u,v,i;
	while(left<=right){
		u=que[left++];
		for(i=G.fir[u];i;i=G.nex[i]){
			v=G.to[i];
			if(dis[v]>dis[u]+G.w[i]){
				dis[v]=dis[u]+G.w[i];
				cnt[v]++;
				if(cnt[v]>n) return 1;
				que[++right]=v;
			}
		}
	}
	return 0;
}

支配树
https://www.luogu.com.cn/problem/P5180

```cpp Graph G,H,T; int uni[N],min[N]; int dfscnt,dfn[N],id[N],fa[N]; int sdom[N],idom[N]; inline int find(int k){ if(k==uni[k]) return k; int ret=find(uni[k]); if(dfn[sdom[min[uni[k]]]]<dfn[sdom[min[k]]]) min[k]="min[uni[k]];" return="" uni[k]="ret;" }="" void="" dfs(int="" u){="" dfn[u]="++dfscnt;id[dfscnt]=u;" for(int="" i="G.fir[u];i;i=G.nex[i])" if(!dfn[g.to[i]])="" fa[g.to[i]]="u,dfs(G.to[i]);" inline="" work(int="" s){="" dfs(s);="" sdom[i]="uni[i]=min[i]=i;" u,i="dfscnt;i">1;i--){ u=id[i]; for(int v,i=H.fir[u];i;i=H.nex[i]){ v=H.to[i]; if(!dfn[v]) continue; find(v); if(dfn[sdom[min[v]]]<dfn[sdom[u]]) sdom[u]="sdom[min[v]];" }="" uni[u]="fa[u];" t.add(sdom[u],u);u="fa[u];" for(int="" v,i="T.fir[u];i;i=T.nex[i]){" v="T.to[i];" find(v);idom[v]="(u==sdom[min[v]])?u:min[v];" t.fir[u]="0;" u,i="2;i<=dfscnt;i++){" u="id[i];" if(idom[u]^sdom[u])="" idom[u]="idom[idom[u]];" int="" ans[n];="" inline="" void="" get_ans(){="" i="dfscnt;i">1;i--) ans[idom[id[i]]]+=++ans[id[i]]; ans[id[1]]++; } ```