首页 > 其他分享 >图论

图论

时间：2024-09-12 11:46:04浏览次数：7  
标签：图论 min int ++ dfn low now

图论

连通性

什么是连通?

任意两点之间有路径使其相互连接。

强连通分量

  • 若一张有向图的节点两两互相可达，则称这张图是强连通的
  • 强连通分量是一个图的一部分是强联通的，则称这是强连通分量

怎么求？

这里给出一种方法：tarjan

  • Tarjan 算法基于对图进行 深度优先搜索。我们视每个连通分量为搜索树中的一棵子树，在搜索过程中，维护一个栈，每次把搜索树中尚未处理的节点加入栈中。
    对于某个节点u，我们需要维护以下变量
  • low[u]，当前节点不经过父亲能返回到的最早的节点是什么
  • dfn[u]，时间戳，表示是第几个被访问到的
  • black[u]，在第几个强连通分量中。

思路：

  • 要是没有时间戳，即没有被访问过，那就遍历这一个点，然后因为当前节点可以遍历到下一个节点，放到栈中，所以low[u]可以是下一个节点或自身的最小值。
  • 否则就是当前节点或者下一个节点可以返回的最小值
  • 最后如果当前节点的时间戳与low相同，则说明走了一圈又绕回来了，那么当前在栈中的就属于当前这个强连通分量。
void tarjan(int x){
	st.push(x);
	dfn[x]=low[x]=++cnt;
	for(int i=head[x];i!=-1;i=a[i].nxt){
		int to=a[i].to;
		if(!dfn[to]){
			tarjan(to);																
			low[x]=min(low[x],low[to]);
		}
		else {
			if(!black[to]){
				low[x]=min(low[x],dfn[to]);
			}
		}
	}
	if(dfn[x]==low[x]){
		black[x]=++sum,q[sum].push_back(x);
		while(st.top()!=x){
			black[st.top()]=sum;
			q[sum].push_back(st.top());
			st.pop();
		}
		st.pop();
	}
}

缩点

  • 把所有强连通分量都缩成一个点就可以了
  • 与强连通分量代码类似

割点

  • 在无向图中将这一点删去后，无法使图强连通。

定义

  • low[u]，当前节点不经过父亲能返回到的最早的节点是什么
  • dfn[u]，时间戳，表示是第几个被访问到的

思路：

  • 因为删去之后无法连通，所以这个点的子节点最早可以到达的点一定会比割点的时间戳要大或相等，不然就可以走其他点过去。
  • 当没有遍历过时，将这一个点遍历，判断它是否满足要求，并且将它的能不通过父节点能到达的最早的点通过子节点更新。
  • 如果遍历过，并且这个点的子节点不是他的父节点，那么更新
  • 最后有一种特殊情况，即当一个点只能通过它到达的节点的数量>=2且它没有父节点，所以无法被上面更新到，如果满足以以上要求，就更新
#include<bits/stdc++.h>
#include<stack>
#include<vector>
using namespace std;
const int N=5e5+10;
struct node{
	int to,nxt;
}a[N<<1];
int n,m,u,v;
int tot,head[N<<1];
void add(int x,int y){
	a[++tot].to=y;
	a[tot].nxt=head[x];
	head[x]=tot;
}
int low[N<<1],dfn[N<<1];
priority_queue<int>q;
int cnt;
int vis[N],flag[N];
void tarjan(int now,int fa){
	int son=0;
	low[now]=dfn[now]=++cnt;
	for(int i=head[now];i;i=a[i].nxt){
		int to=a[i].to;
		if(!dfn[to]){
			++son;
			tarjan(to,now);
			low[now]=min(low[now],low[to]);
			if(low[to]>=dfn[now]&&(!flag[now])&&(fa!=now)){
				flag[now]=1;q.push(-now);
			}
		}
		else if(to!=fa){
			low[now]=min(low[now],dfn[to]);
		}
	}
	if(son>=2&&(!flag[now])&&(fa==now)){
		flag[now]=1;q.push(-now);
     //   cout<<now<<" ";
	}
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL),cout.tie(NULL);
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		cin>>u>>v;
		add(u,v),add(v,u);
	}
	for(int i=1;i<=n;i++){
		if(!dfn[i]){
			tarjan(i,i);
		}
	}
	cout<<q.size()<<'\n';
	while(q.size()){
		cout<<-1*q.top()<<" ";q.pop();
	}
	return 0;
}

割边

  • 在无向图中，删去一点使得整张图不强连通，则这个边为割边
  • 因为这个边为割边，所以一定有这个边连接的父节点的时间戳要比子节点最早能到的时间要小，不能取等是因为，如果通过其他点也能到达，那么则其他边可以到达，则不是割边。
  • 所以满足时间戳要比子节点最早能到的时间要小，连接的两个点的边是割边，将无向图的两个边通过异或的方式标记。
  • 类似割点一样的的改变边，但要注意，标记过时的修改条件是不是反向边。
  • 随后统计答案即可
void tarjan(int x,int edge){
	dfn[x]=low[x]=++cnt;
	for(int i=head[x];i;i=a[i].nxt){
		int to=a[i].to;
		if(!dfn[to]){
			tarjan(to,i);	
            if(low[to]>dfn[x]){
                flag[i]=flag[i^1]=1;
            }															
			low[x]=min(low[x],low[to]);
		}
		else if(i!=(edge^1)){
			low[x]=min(low[x],low[to]);
		}
	}
}

双连通分量

边双连通分量

  • 一个只删掉一条边后仍然可以连通的图
  • 由定义得，边双的边界一定是割边，不然还可以继续扩展
  • 由上面的性质还可以得知每一个点一定只在一个边双中，因为若在两个中就不满足边界是割边。
  • 所以最后把割边去除后，再给每一个没标记过的点，跑一遍不经过标记过点的dfs就可以
#include<bits/stdc++.h>
using namespace std;
const int N=5e6+10;
int n,m,u,v;
int cnt,sum;
int dfn[N],low[N];
struct node{
	int to,nxt;
}a[N<<1];
bool flag[N];
int tot=1,head[N<<1];
void add(int x,int y){
	a[++tot].to=y;
	a[tot].nxt=head[x];
	head[x]=tot;
}
void tarjan(int x,int edge){
	dfn[x]=low[x]=++cnt;
	for(int i=head[x];i;i=a[i].nxt){
		int to=a[i].to;
		if(!dfn[to]){
			tarjan(to,i);	
            if(low[to]>dfn[x]){
                flag[i]=flag[i^1]=1;
            }															
			low[x]=min(low[x],low[to]);
		}
		else if(i!=(edge^1)){
			low[x]=min(low[x],low[to]);
		}
	}
}
int black[N<<1];
vector<int>st[N<<1];
void dfs(int now,int id){
	black[now]=id;
	st[id].push_back(now);
	for(int i=head[now];i;i=a[i].nxt){
		int to=a[i].to;
		if((black[to]||(flag[i])))	continue;
		dfs(to,id);
	}
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		cin>>u>>v;
		if(u==v)    continue;
        add(u,v),add(v,u);
	}
	for(int i=1;i<=n;i++){
		if(!dfn[i])
			tarjan(i,0);
	}
	int ans=0;
	for(int i=1;i<=n;i++){
		if(!black[i]){
			dfs(i,++ans);
		}
	}
	cout<<ans<<'\n';
	for(int i=1;i<=ans;i++){
		cout<<st[i].size()<<" ";
		for(int j=0;j<st[i].size();j++){
			cout<<st[i][j]<<" "; 
		}
		cout<<'\n';
	}
	return 0;
}

点双联通分量

  • 删掉一个点不能使得这一个图不连通。
  • 因为是点，所以有可能一个点出现在两个点双中，观察发现一个点双其实是上一个割点或者根节点到这一个割点的所有点的集合。
  • 所以可以先把经过的点放进栈中，然后当这个节点是根或者割点时弹出。
void tarjan(int now,int fa){
	low[now]=dfn[now]=++cnt;
    if(!head[now]){
        scc[++sum].push_back(now);
    }
	st.push(now);
	for(int i=head[now];i;i=a[i].nxt){
		int to=a[i].to;
		if(!dfn[to]){
			tarjan(to,now);
			low[now]=min(low[now],low[to]);
			if(low[to]>=dfn[now]){
				++sum; 
                int t;
				while(t!=to){
					t=st.top();
					st.pop();
					scc[sum].push_back(t);
				}
				scc[sum].push_back(now);
			}
		}
		else if(to!=fa){
			low[now]=min(low[now],dfn[to]);
		}
	}
}

例题：

BLO-Blockade

观察题目可以得到一些结论

  • 当一个点不是割点时，则不连通的就是它和其他所有点
  • 当一个点是割点时，则可以形象的把他看作一个树的根，那么显然的应该是它的所有"子树"连通块的与其他联通块的乘积，但注意不能重复，所以只需要一个与已经经过过的子树相乘即可
  • 最后注意这样统计的是无序点对，有序点对要乘以2
#include<bits/stdc++.h>
#include<stack>
#include<vector>
#define int long long
using namespace std;
const int N=5e6+10;
struct node{
	int to,nxt;
}a[N<<1];
int n,m,u,v;
int tot,head[N<<1];
void add(int x,int y){
	a[++tot].to=y;
	a[tot].nxt=head[x];
	head[x]=tot;
}
int low[N<<1],dfn[N<<1];
int cnt;
int vis[N],flag[N];
int ans[N];
int siz[N];
void tarjan(int now,int fa){
	int son=0;
	low[now]=dfn[now]=++cnt;
	int sum=0; 
    siz[now]=1;
	for(int i=head[now];i;i=a[i].nxt){
		int to=a[i].to;
		if(!dfn[to]){
			++son;
			tarjan(to,now);
            siz[now]+=siz[to];
			low[now]=min(low[now],low[to]);
			if(low[to]>=dfn[now]){
				ans[now]+=siz[to]*sum;
				sum+=siz[to]; 
			}
		}
		else if(fa!=to){
			low[now]=min(low[now],dfn[to]);
		}
	}
	ans[now]+=(n-sum-1)*sum+(n-1);
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL),cout.tie(NULL);
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		cin>>u>>v;
		add(u,v),add(v,u);
	}
	tarjan(1,1); 
	for(int i=1;i<=n;i++){
		cout<<ans[i]*2<<'\n';
	}
	return 0;
}

受欢迎的牛 G

  • 读题得这道题有传递性，在有向图中，且针对每一个点，可以缩点
  • 当只有一个连通块时，它一定是所有的牛。
  • 当缩完点后，有两个及以上的出度为零，则说明不可能所有牛都喜欢，因为有一个连通块被隔开了。
  • 最后，如果有一个出度为零，那么只有这一个块中的牛，会被所有牛喜欢
#include<bits/stdc++.h>
#include<stack>
#include<vector>
using namespace std;
int n,m,u,v,tot,cnt,tmp;
int head[10005],dfn[10005],low[10005],c[10005],du[2001000],kkk[2000010];
stack<int>st;
vector<int>cok[10005];
bool vis[10005],s[10005];
struct node{
	int to,nxt;
}a[100005];
void add(int x,int y){
	a[++tot].to=y;
	a[tot].nxt=head[x];
	head[x]=tot;
}
void tarjan(int x){
	dfn[x]=low[x]=++tmp;
	st.push(x);
	s[x]=1;
	for(int i=head[x];i;i=a[i].nxt){
		int f=a[i].to;
		if(!dfn[f]){
			tarjan(f);
			low[x]=min(low[x],low[f]);
		}
		else if(s[f]){
			low[x]=min(low[x],dfn[f]);
		}
	}
	if(dfn[x]==low[x]){
		cnt++;
		int d=0;
		while(x!=d){
			d=st.top();
			st.pop();
			s[d]=0;
			kkk[cnt]++;
			c[d]=cnt;
		}
	}
}
int main(){
	cin>>n>>m; 
	for(int i=1;i<=m;i++){
		cin>>u>>v;
		add(u , v);
	}
	for(int i=1;i<=n;i++)
	  if(!dfn[i])  tarjan(i);
	for(int i=1;i<=n;i++){
		for(int j=head[i];j;j=a[j].nxt){
			if(c[i]!=c[a[j].to]){
				du[c[i]]++;
			}
		}
	}
	int num = 0,suu=0;
	for(int i=1;i<=cnt;i++){
		if(!du[i]){
			num=i;
			suu++;
		}
	}
	if(suu>=2)
	cout<<0;
	else 	cout<<kkk[num];
	return 0;
}

拓扑排序

  • 在一个有向无环图中，我们将图中的顶点以线性方式进行排序，使得对于任何的顶点 u 到 v 的有向边 (u,v), 都可以有 u 在 v 的前面。
  • 可以使图变得有序

如何实现？

  • 可以把每一个点的入度统计，然后把入度为零，即前面没有点的点加入队列，然后在队列中，把入度为零的点弹出，然后再将它所连接的点的入度减一
  • 重复以上操作即可
for(int i=1;i<=n;i++){
		if(!ru[i]){
            cout<<i<<" ";
			q.push(i);
		}
	}
	while(!q.empty()){
		int fr=q.front();
		q.pop();
		for(int i=head[fr];i;i=a[i].nxt){
			ru[a[i].to]--;
			if(!ru[a[i].to]){
				cout<<a[i].to<<" ";
				q.push(a[i].to);
			}
		}
	}

例题：

最大食物链计数

  • 把一个点到另一个点的边看作是吃与被吃。
  • 求最大食物链有多少。
  • 考虑在拓扑序下统计答案，对于每一个点都可以由上一个点转移过来，答案累加上一个点。
  • 最后每个出度为0的点累加答案
#include<bits/stdc++.h>
#define mod 80112002
using namespace std;
long long tot,m,head[501000],n,p[510010],cu[510010],u,v,dp[510000];
struct node{
	long long to,nxt;
}a[510000];
void add(int x,int y){
	a[++tot].to=y;
	a[tot].nxt=head[x];
	head[x]=tot;	
}
queue<int>q; 
int main(){
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		cin>>u>>v;
		add(u,v);
		p[v]++;
		cu[u]++;
	}	
	for(int i=1;i<=n;i++){
		if(!p[i]){
			dp[i]++;
			q.push(i);
		}
	}
	while(!q.empty()){
		int fr=q.front();
		q.pop();
		for(int i=head[fr];i;i=a[i].nxt){			
			dp[a[i].to]=(dp[a[i].to]+dp[fr])%mod;
				p[a[i].to]--;		
			if(!p[a[i].to]){
				q.push(a[i].to);				
			}
		}
	}
	long long ans=0;
	for(int i=1;i<=n;i++){
		if(!cu[i]){
			ans=(ans+dp[i])%mod;
		}
	}
	cout<<ans;
	return 0;
}

摄像头

  • 模拟拓扑排序过程即可
#include<bits/stdc++.h>
using namespace std;
int n;
int u,v,m;
int ru[510];
queue<int>q;
struct node{
	int nxt,to;
}a[20010];
int head[10020],tot;
void add(int x,int y){
	a[++tot].to=y;
	a[tot].nxt=head[x];
	head[x]=tot;
}
bool flag[510];
signed main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>u>>m;
        flag[u]=1;
		while(m--){
			cin>>v;
			add(u,v);
			ru[v]++;
		}	
	}
	int ans=0;
	for(int i=1;i<=500;i++){
		if(!ru[i]&&(flag[i])){
			q.push(i);++ans;
		}
	}
	while(q.size()){
		int fr=q.front();
		q.pop();
		for(int i=head[fr];i;i=a[i].nxt){
			int to=a[i].to;
			ru[to]--;
			if(!ru[to]&&(flag[to])){
				++ans;q.push(to); 
			}
		}
	}
	if(ans==n){
		cout<<"YES"; 
	}
	else	cout<<n-ans;
	return 0;
}

最短路

单源最短路

  • 一般使用dijkstra算法，是一种贪心的思路，但是不能运用在有负环的情况下
  • spfa算法，也是一种最短路算法，优点是可以处理负边权，缺点是时间最坏O(nm).

spfa怎么写？

  • spfa 是通过立一个队列，初始时队列里只有起始点，在建立一个表格记录起始点到所有点的最短路径。
  • 然后执行松弛操作，用队列里有的点去刷新起始点到所有点的最短路，如果刷新成功且被刷新点不在队列中则把该点加入到队列最后。重复执行直到队列为空。
void spfa(){
	queue<int>q;
	for(int i=1;i<=n;i++){
		dist[i]=INT_MAX;
	}
	dist[s]=0;
	flag[s]=1;
	q.push(s);
	while(!q.empty()){
		int fr=q.front();
		q.pop();
		flag[fr]=0;	
		for(int i=head[fr];i;i=a[i].nxt){
			int to=a[i].to,w=a[i].w;
			if(dist[to]>w+dist[fr]){
				dist[to]=w+dist[fr];
				if(!flag[to]){
					q.push(to);
				}
				flag[to]=1;
			}
		}
	}
}

dijkstra怎么写？

  • 堆优化之后是具有

    标签：图论,min,int,++,dfn,low,now
    From： https://www.cnblogs.com/lmy333/p/18409895

相关文章

  • 【图论】Johnson全源最短路算法
    ·2024-9-11·最后更新时间2024-9-11作者学会了一个叫做\(Johnson\)的算法，所以就有了这篇博客......Johnson算法是一个高效处理全源最短路的算法其实也很慢，但目前是最高效的为了更加方便你们接下来的学习我希望你们已经掌握了基本的最短路算法（SPFA，Dijsktra，Bellman-Ford，Floyd......
  • 第十一章 图论 Part7
    目录最小生成树算法prim算法适用范围：无向图思路kruskal算法适用范围:无向图思路最小生成树算法prim算法适用范围：无向图思路以将所有点归入最小生成树为目标，每次并入一个，最终生成最小生成树。每次并入的步骤：确定选哪个节点并入（不在最小生成树里的，距离最小生成树（已并入的......
  • 代码随想录day 56 || 图论6
    Prim算法应用场景是主要是找到一个无向连通图的最小生成树，即连接所有节点且权重总和最小的树//prim三部曲//1，找到距离当前最小树最近节点//2，节点入树//3，更新mindist//更新树funcupdateMinDist(edges[][]int,nodeint){ for_,edge:=rangeedges{ ifed......
  • 代码随想录day55 || 图论5
    并查集197图中是否存在有效路径varfather[]intfuncvalidPath(nint,edges[][]int,sourceint,destinationint)bool{ //使用并查集算法，涉及到的操作，包括init，find，issample，join father=make([]int,n) fori,_:=rangefather{//init father[i]=i }......
  • 代码随想录训练营 Day53打卡 图论part04 110. 字符串接龙 105. 有向图的完全可达性 10
    代码随想录训练营Day53打卡图论part04一、卡码110.字符串接龙本题与力扣127题是一样的，所以这里使用力扣127题。字典wordList中从单词beginWord到endWord的转换序列是一个按下述规格形成的序列beginWord->s1->s2->…->sk：    每一对相邻的单词只......
  • 图论篇--代码随想录算法训练营第五十三天打卡| 110. 字符串接龙，105.有向图的完全可达
    110.字符串接龙题目链接：110.字符串接龙题目描述：字典strList中从字符串beginStr和endStr的转换序列是一个按下述规格形成的序列： 序列中第一个字符串是beginStr。序列中最后一个字符串是endStr。 每次转换只能改变一个字符。 转换过程中的中间字符串必须是字典......
  • 第十一章 图论 Part4
    目录任务127.单词接龙思路Kama105.有向图的完全可达性思路463.岛屿的周长思路任务127.单词接龙字典wordList中从单词beginWord到endWord的转换序列是一个按下述规格形成的序列beginWord->s1->s2->...->sk：每一对相邻的单词只差一个字母。对于1<=i<=......
  • 图论板子
    Primtypedefpair<int,int>P;intprim(){intans=0,cnt=0;priority_queue<P,vector<P>,greater<P>>q;fill(d+1,d+n+1,INF);d[1]=0;q.push(P(d[1],1));while(!q.empty()&&cnt<......
  • 代码随想录day 53 || 图论4
    字符串接龙varqueue*list.ListvarvisitMapmap[string]boolfuncmain(){ varcountint fmt.Scanf("%d",&count) varstartStr,endStrstring fmt.Scanf("%s%s",&startStr,&endStr) varstrList=make([]string,count) fo......
  • 第十二章 图论 Part3
    目录任务Kama101.孤岛的总面积思路Kama102.沉没孤岛思路Kama103.水流问题思路Kama104.建造最大岛屿思路心得任务Kama101.孤岛的总面积给定一个由1（陆地）和0（水）组成的矩阵，岛屿指的是由水平或垂直方向上相邻的陆地单元格组成的区域，且完全被水域单元格包围。孤岛是那些位于矩......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99