从0开始的图论

链式前向心

int head[N],cnt,n,m,s,dis[N];
struct edge{int to,value,next;}e[N];
void add(int u,int v,int w){
	e[++cnt].to=v;
	e[cnt].value=w;
	e[cnt].next=head[u];
	head[u]=cnt;
}

最短路

dijkstra板

int head[N],cnt,n,m,s,dis[N];
struct edge{int to,value,next;}e[N];
void add(int u,int v,int w){
	e[++cnt].to=v;
	e[cnt].value=w;
	e[cnt].next=head[u];
	head[u]=cnt;
}
struct Heap{int u,d;}; 
priority_queue<Heap> q;
bool operator < (const Heap& now,const Heap& rhs)
{
	return now.d>rhs.d;
}
inline void init(){
	rep(i,1,n) head[i]=-1;
	cin>>n>>m>>s;
	rep(i,1,m){
		int u,v,w;
		cin>>u>>v>>w;
		add(u,v,w);
	}
}
void dijkstra(){
	rep(i,1,n) dis[i]=2147483647;
	dis[s]=0;
	q.push((Heap){s,dis[s]});
	while(q.size()){
		Heap x=q.top();
		q.pop();
		int u=x.u;
		if(x.d>dis[u]) continue;
		for(int i=head[u];i>0;i=e[i].next){
			int v=e[i].to;
			int w=e[i].value;
			if(dis[v]>dis[u]+w){
				dis[v]=dis[u]+w;
				q.push((Heap){v,dis[v]});
			}
		}
	}
}

最小生成树

struct edge{
	int v,w,next;
}e[N];
int head[N],dis[N],cnt,n,m,tot,now=1,ans;
bool vis[N];
void add(int u,int v,int w){
	e[++cnt].v=v;
	e[cnt].w=w;
	e[cnt].next=head[u]; 	
	head[u]=cnt;
}
void read(){
	cin>>n>>m;
	int u,v,w;
	rep(i,1,m){
		cin>>u>>v>>w;
		add(u,v,w);
		add(v,u,w);
	}
}
int prim(){
	rep(i,2,n) dis[i]=INF;
	for(int i=head[1];i;i=e[i].next){
		dis[e[i].v]=min(dis[e[i].v],e[i].w);
	}
	while(++tot<n){
		int minn=INF;
		vis[now]=1;
		rep(i,1,n){
			if(!vis[i]&&minn>dis[i]){
				minn=dis[i];
				now=i;
			}
		}
		ans+=minn;
		for(int i=head[now];i;i=e[i].next){
			int v=e[i].v;
			if(dis[v]>e[i].w&&!vis[v]) dis[v]=e[i].w;
		}
	}
	return ans;
}

倍增LCA

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=5e5+10;
int fa[N][22],n,m,s,dep[N],vis[N];
vector<int> edge[N];
void dfs(int x){
	vis[x]=1;
	for(int i=0;i<edge[x].size();i++){
		if(!vis[edge[x][i]])
		{
			dep[edge[x][i]]=dep[x]+1;
			fa[edge[x][i]][0]=x;
			dfs(edge[x][i]);
		}
	}
}
signed main(){
	cin>>n>>m>>s;
	for(int i=1;i<n;i++){
		int x,y;
		cin>>x>>y;
		edge[x].push_back(y);
		edge[y].push_back(x);
	}
	dfs(s);
	for(int j=1;j<20;j++) {
		for(int i=1;i<=n;i++)
			fa[i][j]=fa[fa[i][j-1]][j-1];
	}
	for(int i=1;i<=m;i++){
		int x,y;
		cin>>x>>y;
		if(dep[x]>dep[y]) swap(x,y);
		int d=dep[y]-dep[x];
		for(int i=19;i>=0;i--)
			if((d>>i)&1) y=fa[y][i];
		int lca=0;
		if(x==y){
			lca=x;
		}
		else{
		for(int i=19;i>=0;i--)
			if(fa[x][i]!=fa[y][i]){
				x=fa[x][i];
				y=fa[y][i];
			}
		lca=fa[x][0];
		}
		cout<<lca<<endl;
	}
	return 0;
}

邻接表储存
dfs：初始化树结构
倍增：19为常值

for(int j=1;j<20;j++) {
	for(int i=1;i<=n;i++)
		fa[i][j]=fa[fa[i][j-1]][j-1];
}

强连通分量

struct edge{
	int next,value,to;
}e[N];
int n, m;
int head[N],cnt;
int root,dfn[N],low[N],stk[N],top,t,num;
vector<int> dcc[N];

void add(int u, int v){
	e[++cnt].to=v;
	e[cnt].next=head[u];
	head[u]=cnt;
}

void tarjan(int u, int root) {
	dfn[u]=low[u]=++ t;
	stk[++top]=u;
	if(u==root&&!head[u]) {
		dcc[++num].push_back(u);
		return;
	}
	
	for(int i=head[u];i;i=e[i].next) {
		int v=e[i].to;
		if(!dfn[v]) {
			tarjan(v,root);
			low[u]=min(low[u],low[v]);
			if(low[v]>=dfn[u]){
				++num;
				int y;
				do {
					y=stk[top --];
					dcc[num].push_back(y);
				}while(y!=v);
				dcc[num].push_back(u);
			}
		}
		else low[u]=min(low[u],dfn[v]);
	}
}
void work(){
	cin>>n>>m;
	rep(i,1,m){
		int u,v;
		cin>>u>>v;
		if(u==v) continue;
		add(u,v),add(v,u);
	}
	rep(i,1,n){
		if(!dfn[i])
			tarjan(i,i);
	}
}