图论基础知识总结

图论基础知识总结

前言

因为博主太菜，好多之前学过的图论算法都要不记得了，于是开了这篇博文提醒自己要记得复习图论。

代码

#include<bits/stdc++.h>
using namespace std;


#define gc() getchar()
inline int In(){
	char c=gc(); int x=0,ft=1;
	for(;c<'0'||c>'9';c=gc()) if(c=='-') ft=-1;
	for(;c>='0'&&c<='9';c=gc()) x=x*10+c-'0';
	return x*ft;
}
// get cut vertex and bridge
void dfs(int u,int fa){
	dfn[u]=low[u]=++dfs_clock;
	int child=0;
	for(int i=h[u],v;i;i=e[i].nex){
		v=e[i].to;
		if(!dfn[v]){
			dfs(v,u); ++child;
			low[u]=min(low[u],low[v]);
			if(low[v]>=dfn[u]) iscut[u]=1;
			if(low[v]>dfn[u]) // this edge is bridge
		}
		else if(v!=fa) low[u]=min(low[u],dfn[v]);
	}
	if(fa<0&&child==1) iscut[u]=0;
}
// get scc
void tarjan(int u){
	dfn[u]=low[u]=++dfs_clock;
	S[++S_top]=u; ins[u]=1;
	for(int i=h[u],v;i;i=e[i].nex){
		v=e[i].to;
		if(!dfn[v]){
			tarjan(v,u); 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; ++I_cnt;
		do{
			v=S[S_top--];
			id[v]=I_cnt;
			ins[v]=0;
		}while(v!=u);
	}
}
// get bcc
// the bccno of the cut vertex is meaningless
void dfs(int u,int fa){
	dfn[u]=low[u]=++dfs_clock;
	int child=0;
	for(int i=h[u],v;i;i=e[i].nex){
		v=e[i].to; Satus e=(Satus){u,v};
		if(!dfn[v]){
			S.push(e); ++child;
			dfs(v,u); low[u]=min(low[u],low[v]);
			if(low[v]>=dfn[u]){
				iscut[u]=1; ++bcc_cnt;
				bcc[bcc_cnt].clear();
				for(;;){
					Satus x=S.top(); S.pop();
					if(bccno[x.u]!=bcc_cnt){ bcc[bcc_cnt].push_back{x.u}; bccno[x.u]=bcc_cnt; }
					if(bccno[x.v]!=bcc_cnt){ bcc[bcc_cnt].push_back{x.b}; bccno[x.v]=bcc_cnt; }
				}
			}
		}
		else if(dfn[v]<dfn[u]&&v!=pre){
			S.push(e); low[u]=min(low[u],dfn[v]);
		}
	}
	if(pre<0&&child==1) iscut[u]=0;
}
void find_bcc(){
	memset(dfn,0,sizeof(dfn));
	memset(iscut,0,sizeof(iscut));
	memset(bccno,0,sizeof(bccno));
	dfs_clock=bcc_cnt=0;
	for(int i=1;i<=n;++i) if(!dfn[i]) dfs(i,-1);
}
// how to get ecc: 1.do dfs1 to get the bridge
// 2.do dfs2 that don't pass the bridge
// Two_sat
namespace Twosat{
	vector<int> G[N<<1];
	bool mark[N<<1];
	int S[N<<1],S_top;
	inline void init(){
		for(int i=0;i<2*n;++i) G[i].clear();
		memset(mark,0,sizeof(mark));
	}
	bool dfs(int x){
		if(mark[x^1]) return false;
		if(mark[x]) return true;
		mark[x]=true; S[++S_top]=x;
		for(int i=0;i<G[x].size();++i)
		if(!dfs(G[x][i])) return false;
		return true;
	}
	// x = xval or y = yval
	void Add_clause(int x,int xval,int y,int yval){
		x=x*2+xval; y=y*2+yval; G[x^1].push_back(y); G[y^1].push_bask(x);
	}
	bool Solve(){
		for(int i=0;i<n*2;i+=2)
		if(!mark[i]&&!mark[i+1]){
			S_top=0;
			if(!dfs(i)){
				while(S_top>0) mark[S[S_top--]]=false;
				if(!dfs(i+1)) return false;
			}
		}
		return true;
	}
}
// Dijkstra
void djikstra(int s){
	priority_queue<Node> Q;
	for(int i=1;i<=n;++i) d[i]=INF,done[i]=0;
	d[s]=0; done[s]=1; Q.push((Node){s,0});
	while(!Q.empty()){
		Node x=Q.top(); Q.pop();
		int u=x.u; if(done[u]) continue; done[u]=true;
		for(int i=h[u],v;i;i=e[i].nex){
			v=e[i].to;
			if(d[v]>d[u]+e[i].w){
				d[v]=d[u]+e[i].w;
				Q.push((Node){v,d[v]});
			}
		}
	}
}
// SPFA : he has died...
bool SPFA(int s){
	queue<int> Q;
	memset(inq,0,sizeof(inq));
	memset(cnt,0,sizeof(cnt));
	for(int i=1;i<=n;++i) d[i]=INF;
	d[s]=0; Q.push(s); inq[s]=1;
	while(!Q.empty()){
		int u=Q.front(); Q.pop(); inq[u]=0;
		for(int i=h[u],v;i;i=e[i].nex){
			v=e[i].to;
			if(d[v]>d[u]+e[i].w){
				d[v]=d[u]+e[i].w;
				if(!inq[v]){
					Q.push(v); inq[v]=1;
					if(++cnt[v]>n) return true;
				}
			}
		}
	}
	return false;
}
// directed tree
// if there isn' an answer return -1
int Solve(){
	int ans=0,cnt;
	while(1){
		for(int i=1;i<=n;++i) _in[i]=INF;
		for(int i=1;i<=m;++i){
			int u=e[i].u,v=e[i].v;
			if(u!=v&&e[i].w<_in[v]) _in[v]=e[i].w,pre[v]=u;
		}
		for(int i=1;i<=n;++i) if(i!=root&&_in[i]==INF) return -1;
		cnt=0; for(int i=1;i<=n;++i) id[i]=vis[i]=0;
		for(int i=1;i<=n;++i){
			if(i==root) continue;
			ans+=_in[i]; int v=i;
			while(vis[v]!=i&&!id[v]&&v!=root){
				vis[v]=i; v=pre[v];
			}
			if(!id[v]&&v!=root){
				id[v]=++cnt;
				for(int u=pre[v];u!=v;u=pre[u]) id[u]=cnt;
			}
		}
		if(cnt==0) break;
		for(int i=1;i<=n;++i) if(!id[i]) id[i]=++cnt;
		for(int i=1;i<=m;++i){
			int u=e[i].u,v=e[i].v;
			e[i].u=id[u]; e[i].v=id[v];
			if(id[u]!=id[v]) e[i].w-=_in[v];
		}
		root=id[root]; n=cnt;
	}
	return ans;
}
// Kruskal: insert the edge in the order that from min_w to max_w
// Prim: each time find the best point to add into the tree
// Dinic
namespace Dinic{
	int h[N],e_tot=1;
	struct E{ int to,nex,cap,flow; }e[M<<1];
	inline void add(int u,int v,int w){
		e[++e_tot]=(E){v,h[u],w,0}; h[u]=e_tot;
	}
	inline void Add(int u,int v,int w){
		add(u,v,w); add(v,u,0);
	}
	inline void bool bfs(){
		for(int i=s;i<=t;++i) cur[i]=h[i],vis[i]=0;
		queue<int> Q; Q.push(s); d[s]=0; vis[s]=1;
		while(!Q.empty()){
			int u=Q.front(); Q.pop();
			for(int i=h[u],v;i;i=e[i].nex){
				v=e[i].to;
				if(!vis[v]&&e[i].cap-e[i].flow>0){
					Q.push(v); d[v]=d[u]+1; vis[v]=1;
				}
			}
		}
		return vis[t];
	}
	int dfs(int u,int las){
		if(u==t||las==0) return las;
		int flow=0,f;
		for(int i=h[u],v;i;i=e[i].nex){
			v=e[i].to;
			if(d[v]==d[u]+1&&(f=dfs(v,min(las,e[i].cap-e[i].flow)))>0){
				e[i].flow+=f; e[i^1].flow-=f;
				las-=f; flow+=f; if(!las) break;
			}
		}
		return flow;
	}
	inline int max_flow(){
		int flow=0;
		while(bfs()) flow+=dfs(s,INF);
		return flow;
	}
}
int main(){

	return 0;
}