首页 > 其他分享 >图论指南

图论指南

时间：2024-09-22 19:23:09浏览次数：1  
标签：指南 nxt 图论 int edge MAXN front dis

前置知识

在了解图论之前，还需要知道怎么存图。

vector

用 vector<int> G[MAXN] 来存图。$G_i$ 表示从 $i$ 出发，能够到达的点的数组。空间开销相较于链式前向星较大。也可以将 vector 替换为其他 STL 容器，如 list、unordered_set、deque 等。list 的写法空间更优，常数较小，但是 vector 更大众一点。

链式前向星

由于空间小、常数小，深受众多 OIer 的喜爱。本质上是通过跳链的方式，但是不是遍历 $(u\to v)\to(v\to o)$，而是 $(u\to v_i)\to(u\to v_{i+1})$。这种方式遍历图需要至少两个元素：$to,nxt$。$to$ 表示这一条边通向哪里，$nxt$ 表示下一条边是哪里。

这种存图方式还需要一个数组 $head$，$head_i$ 表示 $i$ 的上一条边是哪里，如果 $nxt$ 指向在同一个 $i$ 的 $head_i$，就能够用 $nxt$ 把所有开头为 $i$ 的边串联起来了。下面，给出链式前向星的模板：

struct node{
	int /*from,Kruskal 需要初始点*/to,nxt;
//	ll dis;比如 Dijiestra 需要边权 

}edge[MAXM<<1];//MAXM 表示最多存的边，开 2 倍表示双向边 
int cnt,head[MAXN];//MAXN 表示点数
#define rep(from) for(int i=head[from];i;i=edge[i].nxt)//遍历图
inline void addedge(int from,int to/*,ll dis*/){
	edge[++cnt].to=to;
	edge[cnt].nxt=head[from];
//	edge[cnt].dis=dis;
//	edge[cnt].from=from;
	head[from]=cnt;//存上一条边 
}

邻接矩阵

邻接矩阵用 $dp_{u,v}$ 表示一条边 $(u\to v)$ 的路径。如果无权图的话，用 $1$ 代表有，用 $0$ 代表没有。如果是有权图，用 $-\infty$ 表示。

由于速度慢，通常用于 Floyed 算法，为 dp 式转移。

最短路

Floyed

Floyed 的复杂度是 $\operatorname{O}(n^3)$，本质上是 dp 转移式。枚举初始点 $u$、结尾点 $v$、中转点 $k$，用 $dp_{u,v}=min(dp_{u,v},dp_{u,k}+dp_{k,v})$ 来转移。

ll dp[MAXN][MAXN];//转移
inline void Floyed(){
	for(int u=1;u<=n;++u){
		for(int v=1;v<=n;++v){
			for(int k=1;k<=n;++k){
				dp[u][v]=min(dp[u][v],dp[u][k]+dp[k][v]);//转移式 
			}
		}
	}
}

SPFA

SPFA 的本质在于松弛和 bfs。松弛操作是指 $dis_{u,v}=min(dis_{u,v},dis_{u,k}+w(k,v))$。这和 Floyed 的操作如出一辙。

struct node{
	int to,nxt;
	ll dis;
}edge[MAXM<<1];
int cnt,head[MAXN];
bool vis[MAXN];
ll dis[MAXN];
inline void addedge(int from,int to,ll dis){
	edge[++cnt].to=to;
	edge[cnt].dis=dis;
	edge[cnt].nxt=head[from];
	head[from]=cnt;
} 
inline void SPFA(int s){
	queue<int> q;
	memset(vis,0,sizeof(vis));
	memset(dis,0x3f,sizeof(dis));
	vis[s]=true;
	q.push(s);
	dis[s]=0;//初始化 
	while(!q.empty()){
		int front=q.front();
		q.pop();
		vis[front]=false;//bfs 公式 
		for(int i=head[front];i;i=edge[i].nxt){
			int to=edge[i].to;
			if(dis[to]>dis[front]+edge[i].dis){
				dis[to]=dis[front]+edge[i].dis;//松弛 
				if(!vis[to]){
					q.push(to);//继续扩展，继续松弛 
					vis[to]=true;
				}
			}
		}
	}
}

Dijiestra

Dijiestra 本质上是一种贪心算法，只能够处理无负边权的最短路。

首先，把最短的路径出队，对相应的边进行松弛操作。然后，将相应的边假如队列，继续后续的松弛。

Dijiestra 还有很多种写法，一一介绍：

  • 暴力：直接找最小的节点，时间复杂度为 $\operatorname{O}(n^2+m)$。
  • 堆优化：用二叉堆来维护最小值，可以做到 $m$ 次入队，$n$ 次出队，时间复杂度 $\operatorname{O}((n+m)\log m)$。
  • Fibonacci 堆优化：插入是 $\operatorname{O}(1)$ 的，所以达到了 $\operatorname{O}(m+n\log n)$，但是由于实现难度较高，并且题目基本不用 Fibonacci 堆卡 $\log$，所以不常使用。
  • 线段树优化：将插入堆变成单点修改，查询最小值改成线段树全局查找最小值，时间复杂度 $\operatorname{O}((n+m)\log n)$。

下面给出经典的堆优化和线段树优化代码：

堆优化

struct node{
	int to,nxt;
	ll dis;
}edge[MAXM<<1];
int cnt,head[MAXN];
bool vis[MAXN];
ll dis[MAXN];
inline void addedge(int from,int to,ll dis){
	edge[++cnt].to=to;
	edge[cnt].dis=dis;
	edge[cnt].nxt=head[from];
	head[from]=cnt;
} 
inline void Dijiestra(int s){
	priority_queue<pair<ll,int> > q;
	memset(vis,0,sizeof(vis));
	memset(dis,0x3f,sizeof(dis));
	q.push(make_pair(0ll,s));
	dis[s]=0;
	while(!q.empty()){
		int front=q.top().second;//每次出队的是最小值 
		q.pop();
		if(vis[front]){
			continue;//剪枝 
		}
		vis[front]=true;
		for(int i=head[front];i;i=edge[i].nxt){
			int to=edge[i].to;
			if(dis[to]>dis[front]+edge[i].dis){
				dis[to]=dis[front]+edge[i].dis;
				q.push(make_pair(dis[to],to)));//松弛操作 
			}
		}
	}
}

线段树优化

struct node{
	int to,nxt;
	ll dis;
}edge[MAXM<<1];
int cnt,head[MAXN],pos[MAXN<<2];
bool vis[MAXN];
ll dis[MAXN],ans[MAXN],tree[MAXN<<2];
inline void addedge(int from,int to,ll dis){
	edge[++cnt].to=to;
	edge[cnt].dis=dis;
	edge[cnt].nxt=head[from];
	head[from]=cnt;
} 
inline void push_up(int root){
	if(tree[root<<1]<tree[root<<1|1]){
		tree[root]=tree[root<<1];
		pos[root]=pos[root<<1];
	}else{
		tree[root]=tree[root<<1|1];
		pos[root]=pos[root<<1|1];
	}
}
void build(int root,int l,int r){
	if(l==r){
		tree[root]=INT_MAX;
		pos[root]=l;
		return;
	}
	int mid=(l+r)>>1;
	build(root<<1,l,mid);
	build(root<<1|1,mid+1,r);
	push_up(root); 
}
void change(int root,int pos,ll k,int l,int r){
	if(l==pos&&r==pos){
		tree[root]=k;
		return;
	}
	int mid=(l+r)>>1;
	if(pos<=mid){
		change(root<<1,pos,k,l,mid); 
	}else{
		change(root<<1|1,pos,k,mid+1,r);
	}
	push_up(root);
}
inline void Dijiestra(int s){
	fill(dis+1,dis+n+1,INT_MAX);
	build(1,1,n);//建树 
	dis[s]=0ll;
	for(int i=1;i<=n;++i){
		ans[s]=dis[s];
		ll disu=dis[s];
		change(1,s,ll(INT_MAX)+1ll,1,n);
		for(int j=head[s];j;j=edge[j].nxt){
			int to=edge[j].to;
			if(dis[to]<=INT_MAX&&dis[to]>dis[s]+edge[j].dis){
				dis[to]=dis[s]+edge[j].dis;
				change(1,to,dis[to],1,n);//修改 
			}
		}
		s=pos[1];
	}
}

Johnson

Johnson 的本质是重新赋权。先新建一个虚拟节点 $0$，向其他节点延伸出 $n$ 条边权为 $0$ 的点，用 SPFA 或者 Floyed 跑 $0$ 到其他节点的最短路。重新赋权，比如有边 $u\to v$，长度为 $w$，则重新赋为 $w+dis_u-dis_v$，然后再跑 Dijiestra。

例题1

这一道题目要求的就是中转距离，根据时间多加的点进行 $\operatorname{O}(n)$ 的转移即可。

#include<bits/stdc++.h>
#define MAXN 202
#define INF 1e9
using namespace std;
int f[MAXN][MAXN],a[MAXN];
int main(){
	int n,m,q,p=0;
	scanf("%d %d",&n,&m);
	for(int i=0;i<n;++i){
		scanf("%d",&a[i]);
		for(int j=0;j<n;++j){
			f[i][j]=INF;
		}
		f[i][i]=0;
	}
	while(m--){
		int x,y,len;
		scanf("%d %d %d",&x,&y,&len);
		f[x][y]=f[y][x]=len;
	}
	scanf("%d",&q);
	while(q--){
		int x,y,len;
		scanf("%d %d %d",&x,&y,&len);
		while(a[p]<=len&&p<n){
			for(int i=0;i<n;++i){
				for(int j=0;j<n;++j){
					f[i][j]=f[j][i]=min(f[i][j],f[i][p]+f[p][j]);
				}
			}
			++p;
		}
		if(a[x]>len||a[y]>len||f[x][y]==INF){
			puts("-1");
		}else{
			printf("%d\n",f[x][y]);
		}
	}
	return 0;
}

例题2

很让人坠机的样子，因为建边都建不完。发现题目给的异或并不是“在 C++ 中用 ^ 表示”，而是放了链接，说明这一道题目跟异或的性质有关。

我们发现有一些边可以被其他的边替代，而且按位来算正好是 $n\log n$ 的！再推一下，我们发现形如 $5$ 的二进制是 $101$，那么可以用 $4\oplus 1=100\oplus001=101=5$ 替代。那么，只需要处理位上最高位是 $1$ 的，其他的都可以组合而成。

之后，跑 Dijiestra 就可以了。堆优化比较呛，要吸氧。这里放上线段树优化的代码。

#include<bits/stdc++.h>
#define MAXN 1000001
#define MAXM MAXN*22
using namespace std;
typedef long long ll;
struct node{
	int from,nxt,to;
	ll dis;
}edge[MAXM];
int n,m,c,s,t,cnt,head[MAXN],pos[MAXN<<2];
ll dis[MAXN],ans[MAXN],tree[MAXN<<2];
inline void addedge(int x,int y,ll dis){
	edge[++cnt].to=y;
	edge[cnt].from=x;
	edge[cnt].nxt=head[x];
	edge[cnt].dis=dis;
	head[x]=cnt;
}
inline void push_up(int root){
	if(tree[root<<1]<tree[root<<1|1]){
		tree[root]=tree[root<<1];
		pos[root]=pos[root<<1];
	}else{
		tree[root]=tree[root<<1|1];
		pos[root]=pos[root<<1|1];
	}
}
void build(int root,int l,int r){
	if(l==r){
		tree[root]=INT_MAX;
		pos[root]=l;
		return;
	}
	int mid=(l+r)>>1;
	build(root<<1,l,mid);
	build(root<<1|1,mid+1,r);
	push_up(root); 
}
void change(int root,int pos,ll k,int l,int r){
	if(l==pos&&r==pos){
		tree[root]=k;
		return;
	}
	int mid=(l+r)>>1;
	if(pos<=mid){
		change(root<<1,pos,k,l,mid); 
	}else{
		change(root<<1|1,pos,k,mid+1,r);
	}
	push_up(root);
}
inline void Dijiestra(int s){
	fill(dis+1,dis+n+1,INT_MAX);
	build(1,0,n);
	dis[s]=0ll;
	for(int i=1;i<=n;++i){
		ans[s]=dis[s];
		ll disu=dis[s];
		change(1,s,ll(INT_MAX)+1ll,1,n);
		for(int j=head[s];j;j=edge[j].nxt){
			int to=edge[j].to;
			if(dis[to]<=INT_MAX&&dis[to]>dis[s]+edge[j].dis){
				dis[to]=dis[s]+edge[j].dis;
				change(1,to,dis[to],1,n);
			}
		}
		s=pos[1];
	}
}
int main(){
	scanf("%d %d %d",&n,&m,&c);
	while(m--){
		int x,y;
		ll dis;
		scanf("%d %d %lld",&x,&y,&dis);
		addedge(x,y,dis);
	}
	for(int i=0;i<=n;++i){
		for(int j=1;j<=n;j<<=1){
			if((i^j)<=n){
				addedge(i,i^j,1ll*j*c);
			}
		}
	}
	scanf("%d %d",&s,&t);
	Dijiestra(s);
	printf("%d\n",ans[t]);
	return 0;
}

堆优化的也放上：

#include<bits/stdc++.h>
#define MAXN 1000001
#define MAXM MAXN*22
using namespace std;
typedef long long ll;
struct node{
	int nxt,to;
	ll dis;
}edge[MAXM];
int cnt,head[MAXN],dis[MAXN];
inline void addedge(int x,int y,ll dis){
	edge[++cnt].to=y;
	edge[cnt].nxt=head[x];
	edge[cnt].dis=dis;
	head[x]=cnt;
}
inline void Dijiestra(int s){
	memset(dis,0x3f,sizeof(dis));
	priority_queue<pair<ll,int>,vector<pair<ll,int> >,greater<pair<ll,int> > > q;
	dis[s]=0ll;
	q.push(make_pair(0ll,s));
	while(!q.empty()){
		int front=q.top().second;
		q.pop();
		for(int i=head[front];i;i=edge[i].nxt){
			int to=edge[i].to;
			if(dis[to]>dis[front]+edge[i].dis){
				dis[to]=dis[front]+edge[i].dis;
				q.push(make_pair(dis[to],to));
			}
		}
	}
}
int main(){
	int n,m,c;
	scanf("%d %d %d",&n,&m,&c);
	while(m--){
		int x,y;
		ll dis;
		scanf("%d %d %lld",&x,&y,&dis);
		addedge(x,y,dis);
	}
	for(int i=0;i<=n;++i){
		for(int j=1;j<=n;j<<=1){
			if((i^j)<=n){
				addedge(i,i^j,1ll*j*c);
			}
		}
	}
	int s,t;
	scanf("%d %d",&s,&t);
	Dijiestra(s);
	printf("%lld",dis[t]);
	return 0;
}

树上问题

最小生成树

Kruskal

Kruskal 的本质是不断地加边，直到整个图连通。由于最小的概念，所以要从边权小的开始加，用并查集维护两个点当前能不能够互相到达。时间复杂度 $m(\log m+\log n)$。

struct node{
	int from,to;
	ll dis;
}edge[MAXM<<1];//由于不需要遍历点的下一条边，所以可以不需要 nxt 和 head 
int cnt,fa[MAXN];
inline void addedge(int from,int to,ll dis){
	edge[++cnt].from=from;
	edge[cnt].to=to;
	edge[cnt].dis=dis;
}
inline bool cmp(node x,node y){
	return x.dis<y.dis;
}
inline void prework(){
	for(int i=1;i<MAXN;++i){
		fa[i]=i;
	}
}
int get(int x){
	if(fa[x]==x){
		return x;
	}
	return fa[x]=get(fa[x]);
}
inline void merge(int x,int y){
	fa[get(x)]=get(y);
}
inline ll Kruskal(){
	ll ans=0;
	prework();//初始化 
	sort(edge+1,edge+1+cnt,cmp);//从小到大 
	for(int i=1;i<=cnt;++i){//遍历每一条边 
		int u=edge[i].from,v=edge[i].to;
		if(get(u)!=get(v)){//两个节点需要加边 
			merge(u,v);
			ans+=edge[i].dis;
		}
	}
	return ans;
}

Prim

Prim 的本质是加点。每一次加上距离最小的点，然后更新。可以使用类似于 Dijiestra 的优化。

struct node{
	int from,to,nxt;
	ll dis;
}edge[MAXM<<1];
int n,cnt,head[MAXN];
ll dis[MAXN];
bool vis[MAXN];
inline void addedge(int from,int to,ll dis){
	edge[++cnt].from=from;
	edge[cnt].to=to;
	edge[cnt].dis=dis;
	edge[cnt].nxt=head[from];
	head[from]=cnt;
}
inline ll Prim(){
	memset(dis,0x3f,sizeof(dis));
	memset(vis,0,sizeof(vis));
	priority_queue<pair<ll,int> > q;
	q.push(make_pair(0ll,1));//通常从 1 开始 
	dis[1]=0ll;
	ll ans=0;
	for(int i=1;i<n&&!q.empty();++i){
		int front=q.top().second;
		q.pop();
		if(vis[front]){
			--i;
			continue;
		}
		vis[front]=true;
		ans+=dis[front];//当前的 dis
		for(int i=head[front];i;i=edge[i].nxt){
			int to=edge[i].to;
			if(dis[to]>edge[i].dis){//从三角形不等式变成了介个样子 
				dis[to]=edge[i].dis;
				q.push(make_pair(dis[to],to));
			}
		} 
	}
	return ans;
}

通常来讲，Prim 的时间复杂度为 $(n+m)\log m$，Kruskal 的时间复杂度为 $m(\log n+\log m)$，Prim 应用于稠密图，Kruskal 应用于稀疏图。但是 Prim 在稠密图上只是理论比 Kruskal 更优，因为 Kruskal 有玄学复杂度的并查集，时快时慢，真正也没见得比 Kruskal 优。所以，通常我们使用 Kruskal。

LCA

LCA 是一个经典的例题，可以用于树论，也可以用于图论。通常有两种算法：倍增算法和 Tarjan。

倍增

倍增的方式是预处理出 $fa_{i,j}$ 表示 $i$ 向上跳 $2^j$ 步所到达的节点。这个可以使用 dfs 预处理，时间复杂度 $n\log n$。然后单次询问让更深的节点通过倍增能够组合成任何数的性质跳到同一层，然后不断往上跳，跳到相同为止。时间复杂度 $\log n$，总时间复杂度 $(n+m)\log n$。

struct node{
	int to,nxt;
}edge[MAXM<<1];
int n,cnt,head[MAXN]; 
int dep[MAXN],fa[MAXN][MAXK];
inline void addedge(int x,int y){
	edge[++cnt].to=y;
	edge[cnt].nxt=head[x];
	head[x]=cnt;
}
void dfs(int now,int pa){
	fa[now][0]=fa;
	dep[now]=dep[fa]+1;
	for(int i=1;i<MAXK;++i){
		fa[now][i]=fa[fa[now][i-1]][i-1];//更新向上跳 
	}
	for(int i=now;i;i=edge[i].nxt){
		int to=edge[i].to;
		if(to!=pa){
			dfs(to,now);//dfs 下一个节点 
		}
	}
}
inline int lca(int x,int y){
	if(dep[x]>dep[y]){
		swap(x,y);//深的在下面 
	}
	for(int i=0;i<MAXK;++i){
		if(dep[fa[y][i]]>=dep[x]){
			y=fa[y][i];
		} 
	} 
	if(x==y){
		return x;
	}
	for(int i=0;i<MAXK;++i){
		if(fa[x][i]!=fa[y][i]){
			x=fa[x][i];
			y=fa[y][i];//一起向上跳 
		}
	}
	return x;
}

Tarjan

Tarjan 是一种离线的算法，要使用并查集来维护。

首先，要接受输入边 InputEdge 和查询边 QueryEdge，并区分开来。QueryEdge 需要反向加入。

用 dfs 遍历。如果遍历到一条节点，使用 $vis$ 记录每个节点有没有访问过，$fa$ 记录祖先节点。

当一个节点还在遍历根节点的时候，就设置父节点为自己，否则设置为不断往上的节点。

如果发现该点访问完了，而且另一个节点也访问完了，那么父节点就是答案。

struct node{
	int from,to,nxt;
}edge[MAXM<<1];
struct query_node{
	int from,to,nxt,lca;
}QueryEdge[MAXQ<<1];
int head[MAXN],QueryHead[MAXN];
int cnt,QueryCnt;
int fa[MAXN];
bool vis[MAXN];
inline void prework(){
	for(int i=1;i<MAXN;++i){
		fa[i]=i;
		vis[i]=false;
	}
}
int get(int x){
	if(fa[x]==x){
		return x;
	}
	return fa[x]=get(fa[x]);
}
void Tarjan(int u){
	fa[u]=u;//设置父节点 
	vis[u]=true;
	for(int i=head[u];i;i=edge[i].nxt){
		int v=edge[i].to;
		if(!vis[v]){
			Tarjan(v);//递归 
			fa[to]=u;//设置父节点 
		}
	}
	for(int i=QueryHead[u];i;i=QueryEdge[i].nxt){
		int v=QueryEdge[i].to;//遍历查询 
		if(vis[v]){
			QueryEdge[i-1].lca=QueryEdge[i].lca=get(edge[i].to);
		}
	}
}

注意，本 Tarjan 代码复杂度其实还需要套上一个并查集的复杂度，其实有 $\operatorname{O}(n+m)$ 的实现，于此（全英文警告）。

例题

有一些较小边权的边不一定会走过去，考虑用 Kruskal 换种做法，跑最大生成树。

求出这个后，题目转化成求两个点之间路径的最小边权，由于是唯一的，但是直接跑会超时，所以考虑再处理一个 $minv$ 表示最小值，跑 LCA。

#include<bits/stdc++.h>
#define MAXN 10001
#define MAXM 50005
#define MAXK 21
#define INF 2147483647
using namespace std;
struct node{
	int from,to,next,dis;
}a[MAXM],edge[MAXM<<1];
int n,m,q,cnt,head[MAXN],deep[MAXN],fa[MAXN][MAXK],dis[MAXN][MAXK],fa[MAXN];
bool vis[MAXN];
inline void addedge(int from,int to,int dis){
	edge[++cnt].next=head[from];
	edge[cnt].from=from;
	edge[cnt].to=to;
	edge[cnt].dis=dis;
	head[from]=cnt;
}
inline bool cmp(const node &x,const node &y){
	return x.dis>y.dis;
}
inline int get(int x){
	if(fa[x]==x){
		return x;
	}
	return fa[x]=get(fa[x]);
}
inline void merge(int x,int y){
	fa[get(x)]=get(y);
}
inline void Kruskal(){
	sort(a+1,a+m+1,cmp);
	for(int i=1;i<=n;++i){
		fa[i]=i;
	}
	for(int i=1;i<=m;++i){
		if(get(a[i].from)!=get(a[i].to)){
			merge(a[i].from,a[i].to);
			addedge(a[i].from,a[i].to,a[i].dis);
			addedge(a[i].to,a[i].from,a[i].dis);
		}
	}
}
inline void dfs(int now){
	vis[now]=true;
	for(int i=head[now];i;i=edge[i].next){
		int to=edge[i].to;
		if(vis[to]){
			continue;
		}
		deep[to]=deep[now]+1;
		fa[to][0]=now;
		dis[to][0]=edge[i].dis;
		dfs(to);
	}
}
inline int lca(int x,int y){
	if(get(x)!=get(y)){
		return -1;
	}
	if(deep[x]>deep[y]){
		swap(x,y);
	}
	int ans=INF;
	for(int i=MAXK-1;i>=0;--i){
		if(deep[fa[y][i]]>=deep[x]){
			ans=min(ans,dis[y][i]);
			y=fa[y][i];
		}
	}
	if(x==y){
		return ans;
	}
	for(int i=MAXK-1;i>=0;--i){
		if(fa[x][i]!=fa[y][i]){
			ans=min(ans,min(dis[x][i],dis[y][i]));
			x=fa[x][i];
			y=fa[y][i];
		}
	}
	return min(ans,min(dis[x][0],dis[y][0]));
}
int main(){
	scanf("%d %d",&n,&m);
	for(int i=1;i<=m;++i){
		scanf("%d %d %d",&a[i].from,&a[i].to,&a[i].dis);
	}
	Kruskal();
	for(int i=1;i<=n;++i){
		if(!vis[i]){
			deep[i]=0;
			dfs(i);
			fa[i][0]=i;
			dis[i][0]=INF;
		}
	}
	for(int i=1;i<MAXK;++i){
		for(int j=1;j<=n;++j){
			fa[j][i]=fa[fa[j][i-1]][i-1];
			dis[j][i]=min(dis[j][i-1],dis[fa[j][i-1]][i-1]);
		}
	}
	scanf("%d",&q);
	while(q--){
		int x,y;
		scanf("%d %d",&x,&y);
		printf("%d\n",lca(x,y));
	}
	return 0;
}

其他

拓扑排序

拓扑排序是基于拓扑序进行的排序。比如 $u\to v$ 有一条边，那么则称 $u$ 的拓扑序大于 $v$。

拓扑排序的思想是找出入度为 $0$ 的点，然后将这个点删除，再去找入度为 $0$ 的点，直到没有入度为 $0$ 的点（有环）或者图空了（没环）。

struct node{
	int to,nxt;
}edge[MAXM<<1];
int cnt,head[MAXN],indeg[MAXN];
bool vis[MAXN];
inline void addedge(int from,int to,int dis){
	edge[cnt].to=to;
	edge[++cnt].nxt=head[from];
	head[from]=cnt;
}
inline bool Topusort(){
	queue<int> q;
	for(int i=1;i<MAXN;++i){
		if(!indeg[i]){
			q.push(i);//加入入度为 0 的点 
		}
	}
	while(!q.empty()){
		int front=q.front();
		q.pop();
		for(int i=head[front];i;i=edge[i].nxt){//遍历相关的点 
			int to=edge[i].to;
			--indeg[to];
			if(!indeg[to]){
				q.push(to);//加入入度为 0 的点 
			}
		}
	}
	for(int i=1;i<MAXN;++i){
		if(indeg[i]){
			return true;//如果还有，那就有环 
		}
	}
	return false;//没有环 
}

例题

发现停靠了的节点的等级一定大于其他没有停靠的节点，可以把这个等级看作是拓扑序，较优先的节点向靠后的节点连边，然后跑 Topu 即可。

#include<iostream>
#include<vector>
#include<queue>
#define MAXN 1001
using namespace std;
int n,m,a[MAXN],indeg[MAXN];
vector<int> G[MAXN];
bool uni[MAXN],vis[MAXN][MAXN];
inline void addedge(int from,int to){
	G[from].push_back(to);
	++indeg[to];
	vis[from][to]=true;
}
inline int Topusort(){
	queue<pair<int,int> > q;
	int ans=1;
	for(int i=1;i<=n;++i){
		if(!indeg[i]){
			q.push(make_pair(i,1));
		}
	}
	while(!q.empty()){
		int from=q.front().first;
		int step=q.front().second;
		q.pop();
		for(int i=0;i<G[from].size();++i){
			int to=G[from][i];
			--indeg[to];
//			ans=max(ans,step+1);
			if(!indeg[to]){
				q.push(make_pair(to,step+1));
				ans=max(ans,step+1);
			}
//			cout<<to<<" "<<step+1<<endl;
		}
	}
	return ans;
}
int main(){
	scanf("%d %d",&n,&m);
	while(m--){
		int k;
		scanf("%d",&k);
		for(int i=1;i<=k;++i){
			scanf("%d",&a[i]);
			uni[a[i]]=true;
		}
		for(int i=a[1];i<=a[k];++i){
			if(!uni[i]){
				for(int j=1;j<=k;++j){
					if(!vis[a[j]][i]){
						addedge(a[j],i);
					}
				}
			}
		}
		for(int i=1;i<=k;++i){
			uni[a[i]]=false;
		}
	}
	printf("%d",Topusort());
	return 0;
}

标签：指南,nxt,图论,int,edge,MAXN,front,dis
From： https://www.cnblogs.com/hisy/p/18425731

相关文章

  • 全面指南：使用JMeter进行性能压测与性能优化（中间件压测、数据库压测、分布式集群压测、
    目录一、性能测试的指标1、并发量2、响应时间3、错误率4、吞吐量5、资源使用率二、压测全流程三、其他注意点1、并发和吞吐量的关系2、并发和线程的关系四、调优及分布式集群压测（待仔细学习）1.线程数量超过单机承载能力时的解决方案2.如何搭建分布式集群3.实施......
  • Cursor 使用技巧指南
    引言在过去的1周里，我使用Cursor完成了1个chrome插件、1个内部查询系统的开发，这些经验让我总结出了5个使用Cursor的技巧，这些技巧不仅能提升你的使用体验，还能帮你实现免费使用最强代码AI。并别忘了点赞和收藏。CursorAi开发的AI浏览器侧边栏完整源码地址（0积分下载）：https:/......
  • 如何掌握 MERN 堆栈：全栈开发人员指南
    MERN堆栈（MongoDB、Express.js、React.js、Node.js）已成为全堆栈Web开发最流行的技术之一。作为一名开发人员，学习MERN堆栈可以打开一个充满机遇的世界，并让您走上构建强大的动态Web应用程序的道路。以下是您如何掌握MERN堆栈并将您的全堆栈开发技能提升到新水平的方法。了解......
  • 如何在 Ruby 中使用互斥体：综合指南
    介绍并发是编程中的强大工具，可以让多个线程同时执行代码。然而，这种权力也伴随着安全管理共享资源的责任。在ruby中，mutex（互斥的缩写）是确保一次只有一个线程可以访问资源、防止潜在的数据损坏或不可预测的行为的关键组件。在这篇博客中，我们将探索如何在ruby中使用mutex，并通过示......
  • MacOS升级Ruby版本的完整指南
    前言随着技术的快速发展，保持开发环境的最新状态变得至关重要。对于Ruby开发者，升级Ruby版本不仅能获得性能提升，还能享受更多的功能特性和更高的安全性。特别是在移动端开发中，Ruby和RubyonRails的应用非常广泛，因此确保你的Ruby版本与最新标准一致尤为重要。本文将详细介绍如......
  • 在 Effect-TS 中组合选项：实用指南
    effect-ts提供了几种在函数式编程上下文中组合可选值或选项的强大方法。无论您想要将多个选项配对在一起还是将选项内的函数应用于其他值，该库都提供了多种方法来简化这些操作。在本文中，我们将探讨组合选项的四个关键函数：o.product、o.productmany、o.all和o.ap。示例1：使......
  • 在 NGINX 上托管 Angular 应用程序的终极指南
    在nginx服务器上托管angular应用程序可以增强性能，提供更好的安全性，并为生产环境提供更轻松的配置。以下是在nginx上部署angular应用程序的分步指南。先决条件已安装nginx：确保您的服务器上安装了nginx。您可以使用以下命令将其安装在基于linux的系统上：狂欢sudoaptupd......
  • 动态编程变得简单：带有 JavaScript 示例的初学者指南
    通过javascript中的动态编程释放高效解决问题的能力。介绍您想提高编程中解决问题的能力吗？动态规划（dp）是一种强大的技术，可以帮助您高效地解决复杂问题。本初学者指南将通过javascript示例向您介绍动态编程，使其易于掌握并应用于实际场景。您将学到什么：动态规划的基本概念......
  • 使用 Lerna 掌握 Monorepos：综合指南
    简介管理具有多个相互依赖的包的大型项目对许多开发团队来说是一个挑战。传统方法通常涉及为每个包使用多个存储库，这可能会导致代码维护、依赖项管理和协作方面的开销。lerna是一款功能强大的javascript工具，通过引入一种有效的方法来管理monorepos（在单个代码库中托管多个包的......
  • SpringBoot学习指南
    文章目录一、为什么要学习SpringBoot二、SpringBoot介绍2.1约定优于配置2.2SpringBoot中的约定三、SpringBoot快速入门3.1快速构建SpringBoot3.1.1选择构建项目的类型3.1.2项目的描述3.1.3指定SpringBoot版本和需要的依赖3.1.4导入依赖3.1.5......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99