首页 > 其他分享 >[图论]强连通分量

[图论]强连通分量

时间：2023-07-27 15:36:48浏览次数：37  
标签：cnt 连通 int 图论 ins dfn low dp 分量

强连通分量

一、强连通分量

1.DFS森林和强连通分

(1)DFS Forest

  • Tree Edge指树边
  • Back Edge指连向祖先的边(返祖边)
  • Forward Edge指连向子孙的边(前向边，它主要是在搜索的时候遇到了一个已经访问过的结点，但是这个结点 并不是 当前结点的祖先。)
  • Cross Edge指连向树其他分支的边(横插边,它主要是在搜索的时候遇到了一个已经访问过的结点，但是这个结点 并不是 当前结点的祖先。)
  • 在无向图只存在Tree Edge和Back Edge

image

(2)强连通分量SCC(Strongly Connected Component)

image

强连通：u存在到达v的路径，v存在到达u的路径，我们称u、v是强连通的（如图中绿框里面的）

推论：\(\begin{cases} u,v强连通\\ v,w强连通\end{cases} \tag{1}\) ==> \(u,w\)强连通

2.SCC的Tarjan和Kosaraju算法

(1)Tarjan 算法求强连通分量

我们考虑把它切成一块一块的强连通分类，能切就切

image

  • 不能连上去
  • 不能连向前面未切的点

对于每个结点\(u\)我们需要维护：

  1. \(dfn\):\(dfs\)遍历时候结点u被搜到的次序

  2. \(low\)：在\(u\)的子树中能回溯到的最早的已经在栈中的结点。设以\(u\)为根的子树为\(subtree_u\)。\(low_u\) 定义为以下结点的\(dfn\)的最小值：\(subtree_u\)中的结点；从\(subtree_u\)通过一条不在搜索树上的边能到达的结点。

    一个结点的子树内结点的 \(dfn\) 都大于该结点的 \(dfn\)。

每当找到一个强连通元素，就按照该元素包含结点数目让栈中元素出栈。

在搜索过程中，对于结点\(u\)和与其相邻的结点(\(v\)不是\(u\)的父节点)考虑 3 种情况：

  1. \(v\)未被访问：继续对\(v\)进行深度搜索。在回溯过程中，用\(low_v\)更新\(low_u\)。因为存在从\(u\)到 \(v\)的直接路径，所以\(v\)能够回溯到的已经在栈中的结点,\(u\)也一定能够回溯到。
  2. \(v\)被访问过，已经在栈中：根据 low 值的定义，用\(dfn_v\)更新\(low_v\)。
  3. \(v\)被访问过，已不在栈中：说明\(v\)已搜索完毕，其所在连通分量已被处理，所以不用对其做操作。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N = 101000;
vector<int>edge[N];
int n,m;
int dfn[N],low[N],ins[N],idx,bel[N],cnt;
//         low记这个子树里面能跳到的dfn最小的，且未被切掉的(ins[u] = true)
stack<int>stk;
vector<vector<int>>scc;
void dfs(int u)
{
	dfn[u] = low[u] = ++idx;
	ins[u] = true;
	stk.push(u);//还没被切掉的点
	for(auto v:edge[u])
	{
		// if(!dfn[v]){
		// 	dfs(v);
		// 	low[u] = min(low[u],low[v]);
		// }
		// else{
		// 	if(ins[v])low[u] = min(low[u],dfn[v]);
		// }

		
		if(!dfn[v])dfs(v);
		if(ins[v])low[u] = min(low[u],low[v]);
	}
	if(dfn[u] == low[u]){
		vector<int>c;
		++cnt;
		while(1)
		{
			int v = stk.top();
			c.push_back(v);
			ins[v] = false;
			bel[v] = cnt;
			stk.pop();
			if(u==v)break;
		}
		sort(c.begin(), c.end());
		scc.push_back(c);
	}

}

int main()
{
	cin>>n>>m;
	for(int i = 1;i<=m;i++)
	{
		int u,v;
		cin>>u>>v;
		edge[u].push_back(v);
	}

	for(int i = 1;i<=n;i++)
	{
		if(!dfn[i])dfs(i);
	}
	sort(scc.begin(),scc.end());
	for(auto c:scc)
	{
		for(auto u:c)
		{
			cout<<u<<" ";
		}
		cout<<"\n";
	}
}

(2)Kosaraju 算法

依靠2次DFS实现：

先DFS一遍：在回溯时候给出点编号，得到出栈顺序(即后序遍历)。

第二次DFS：对反图dfs,这样遍历到的所有点的集合就是一个强连通分量。

❗重要的几个结论

  1. DAG(有向无环图)出栈顺序是反图的拓扑序
  2. 有向图 SCC缩点(不考虑强连通分量内部的连边，只考虑强连通分量与强连通分量之间的连边)之后就是一个DAG
  3. 最后一个出栈的一定是源点(入度为0的点)
  4. Tarjan的SCC的点的编号是反向的拓扑序

image

反着搜：6 2 3 9 7 4 14 12 13 10 15 11 5 1 0 8

image

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

const int N = 101000;
vector<int>edge[N],erev[N];
vector<int>c,out;
int n,m;
bool vis[N];
vector<vector<int>>scc;
void dfs(int u)
{
	vis[u] = true;
	for(auto v:edge[u])
	{
		if(!vis[v])dfs(v);
	}
	out.push_back(u);
}


void dfs2(int u)
{
	vis[u] = true;
	for(auto v:erev[u])
	{
		if(!vis[v])dfs2(v);
	}
	c.push_back(u);
}


int main()
{
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>n>>m;
	for(int i = 1;i<=m;i++)
	{
		int u,v;
		cin>>u>>v;
		edge[u].push_back(v);
		erev[v].push_back(u);
	}

	for(int i = 1;i<=n;i++)
	{
		if(!vis[i])dfs(i);
	}
	reverse(out.begin(),out.end());
	memset(vis,false,sizeof(vis));
	for(auto u: out)
	{
		if(!vis[u])
		{
			c.clear();
			dfs2(u);
			sort(c.begin(),c.end());
			scc.push_back(c);
		}
	}
	sort(scc.begin(),scc.end());
	for(auto c:scc)
	{
		for(auto u:c)
		{
			cout<<u<<" ";
		}
		cout<<endl;
	}
		
}

(3)例题：HAOI2006, 受欢迎的牛

看有多少点，所有点都可达

  • 对于DAG来说，唯一汇点是所有点都可达
  • 对于一般图来说，它SCC缩点之后是一个DAG，那么它要所有点都可达它，它必须是缩完点之后的唯一汇点。之后再去看SCC里面有多少个点。
//有多少个点，所有点都可达
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N = 101000;
vector<int>edge[N];
int n,m;
int dfn[N],low[N],ins[N],idx,bel[N],cnt,sz[N];//sz：每个强连通分量的size
//         low记这个子树里面能跳到的dfn最小的，且未被切掉的(ins[u] = true)
int outd[N];//每个强连通分量它的出度
stack<int>stk;
void dfs(int u)
{
	dfn[u] = low[u] = ++idx;
	ins[u] = true;
	stk.push(u);//还没被切掉的点
	for(auto v:edge[u])
	{
		if(!dfn[v])dfs(v);
		if(ins[v])low[u] = min(low[u],low[v]);
	}
	if(dfn[u] == low[u]){
		++cnt;
		while(1)
		{
			int v = stk.top();
			ins[v] = false;
			bel[v] = cnt;
			sz[cnt]++;
			stk.pop();
			if(u==v)break;
		}
	}

}

int main()
{
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	
	cin>>n>>m;
	for(int i = 1;i<=m;i++)
	{
		int u,v;
		cin>>u>>v;
		edge[u].push_back(v);
	}

	for(int i = 1;i<=n;i++)
	{
		if(!dfn[i])dfs(i);
	}
	for(int u = 1;u<=n;u++)
	{
		for(auto v : edge[u])
		{
			if(bel[u] != bel[v])
				outd[bel[u]]++;
		}
	}

	int cnts = 0,cntv = 0;
	for(int i = 1;i<=cnt;i++)
	{
		if(outd[i]==0)
		{
			cnts++;
			cntv += sz[i];
		}
	}
	if(cnts>=2)//有两个汇点，这两个汇点之间是不可达的
		cout<<0<<"\n";
	else
		cout<<cntv<<"\n";
}

3.SCC缩点和DP

例题1：ZJOI2007, 最大半连通子图

思路：

对于DAG来说，我们找最大半连通子图就是找一条最长路。

那么对于一般图，我们考虑缩点。缩点之后转化为带权的求最长路问题。

步骤：

  1. SCC缩点
  2. DP
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N = 101000;
vector<int>edge[N];
int n,m,cnt,mod;;
int dfn[N],low[N],ins[N],idx,bel[N];
//         low记这个子树里面能跳到的dfn最小的，且未被切掉的(ins[u] = true)
stack<int>stk;
vector<int>vec[N];
int dp[N],way[N];
bool vis[N];
void dfs(int u)
{
	dfn[u] = low[u] = ++idx;
	ins[u] = true;
	stk.push(u);//还没被切掉的点
	for(auto v:edge[u])
	{
		if(!dfn[v])dfs(v);
		if(ins[v])low[u] = min(low[u],low[v]);
	}
	if(dfn[u] == low[u]){
		++cnt;
		while(1)
		{
			int v = stk.top();
			vec[cnt].push_back(v);//记录每个强连通分量有哪些点
			ins[v] = false;
			bel[v] = cnt;
			stk.pop();
			if(u==v)break;
		}
	}
}

int main()
{
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);

	cin>>n>>m>>mod;
	for(int i = 1;i<=m;i++)
	{
		int u,v;
		cin>>u>>v;
		edge[u].push_back(v);
	}

	for(int i = 1;i<=n;i++)
		if(!dfn[i])dfs(i);

	int ans = 0,w = 0;
	for(int i = 1;i<=cnt;i++)
	{
		way[i] = 1;
		dp[i] = 0;
		for(int u : vec[i])
		{
			for(int v :edge[u])
			{
				if(!vis[bel[v]]&&bel[v]!=i)	//注意缩完点之后连边注意重边不要重复计算
				{
					vis[bel[v]] = true;
					if(dp[bel[v]]>dp[i])
						dp[i] = dp[bel[v]],way[i] = 0;
					if(dp[bel[v]]==dp[i])
						way[i] = (way[i]+way[bel[v]])%mod;
				}
			}
		}
		dp[i] += vec[i].size();
		if(dp[i]>ans)
			ans = dp[i],w = 0;
		if(dp[i]==ans)
			w = (w+way[i])%mod;
		for(int u : vec[i])
			for(int v :edge[u])
				vis[bel[v]] = false;

	}
	cout<<ans<<"\n";
	cout<<w<<"\n";

}

写法2：

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

const int N = 101000;
vector<int>edge[N];
int n,m,mod;
int cnt,idx;
int dfn[N],low[N],ins[N],bel[N];
int dp[N],vis[N],way[N];
int ans,w,T;
stack<int>stk;


void dfs(int u)
{
	dfn[u] = low[u] = ++idx;
	ins[u] = true;
	stk.push(u);

	for(auto v:edge[u])
	{
		if(!dfn[v])dfs(v);
		if(ins[v])low[u] = min(low[u],low[v]);
	}
	if(dfn[u]==low[u])
	{
		++cnt;
		int sz = 0;
		dp[cnt] = 0;
		way[cnt] = 1;
		++T;
		vis[cnt] = T;
		while(1)
		{
			int v = stk.top();
			stk.pop();
			ins[v] = false;
			bel[v] = cnt;
			sz++;
			for(auto w:edge[v])
			{
				if(vis[bel[w]]!=T&&bel[w]!=0)
				{
					vis[bel[w]] = T;
					if(dp[bel[w]]>dp[cnt])
						dp[cnt] = dp[bel[w]],way[cnt] = way[bel[w]];
					else if(dp[bel[w]]==dp[cnt])
						way[cnt] = (way[cnt]+way[bel[w]])%mod;
				}
			}
			if(u==v)break;
		}
		dp[cnt] += sz;
		if(dp[cnt]>ans)
			ans = dp[cnt],w = way[cnt];
		else if(dp[cnt]==ans)
			w = (w+way[cnt])%mod;
	}
}


void tarjan()
{
	for(int i = 1;i<=n;i++)
		if(!dfn[i])dfs(i);
}


int main()
{
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>n>>m>>mod;
	for(int i = 1;i<=m;i++)
	{
		int u,v;
		cin>>u>>v;
		edge[u].push_back(v);
	}
	tarjan();
	cout<<ans<<"\n";
	cout<<w<<"\n";
	return 0;
}

例题2：APIO2009, ATM

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

const int N = 501000;
vector<int>edge[N];
int n,m;
int dfn[N],low[N],ins[N],idx,bel[N],cnt;
//         low记这个子树里面能跳到的dfn最小的，且未被切掉的(ins[u] = true)
stack<int>stk;
int val[N],bar[N];
ll dp[N];
void dfs(int u)
{
	dfn[u] = low[u] = ++idx;
	ins[u] = true;
	stk.push(u);//还没被切掉的点
	for(auto v:edge[u])
	{
		if(!dfn[v])dfs(v);
		if(ins[v])low[u] = min(low[u],low[v]);
	}
	if(dfn[u] == low[u]){
		++cnt;
		ll sval = 0;
		bool sbar = false;
		dp[cnt] = -(1ll<<60);
		while(1)
		{
			int v = stk.top();
			stk.pop();
			ins[v] = false;
			bel[v] = cnt;
			sval += val[v];
			sbar |= bar[v];
			for(auto w:edge[v])
			{
				if(bel[w]!= cnt && bel[w] != 0)
				{
					dp[cnt] = max(dp[cnt],dp[bel[w]]);
				}
			}
			if(u==v)break;
		}
		if(sbar)dp[cnt] = max(dp[cnt],0ll);
		dp[cnt] += sval;
	}
}
int main()
{
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);

	cin>>n>>m;
	for(int i = 1;i<=m;i++)
	{
		int u,v;
		cin>>u>>v;
		edge[u].push_back(v);
	}
	for(int i = 1;i<=n;i++)
		cin>>val[i];
	int s,p;
	cin>>s>>p;
	for(int i = 1;i<=p;i++)
	{
		int x;
		cin>>x;
		bar[x] = 1;
	}
	dfs(s);
	cout<<dp[bel[s]]<<"\n";
}

例题3：SDOI2010, 所驼门王的宝藏

思路：首先思考一下怎么去建图？

一共有\(N^2\)个点，如果所有的可达信息都建出来，这复杂度太高了。

那怎么办呢？考虑建立辅助结点。

比如有一个横向的传送门，它可以到这一行所有的点。那么我们考虑先建立一个辅助点，这个辅助点向这一行所有点连边，再把这个有横向传送门的点连向辅助点。这样就可以实现，该点先到辅助点，辅助点再到所有点。

注意点：

  1. 统计size的时候注意不要把辅助点加进去了。
  2. 记录编号数组稍微开大一点(至少开两倍)，因为我们还要记录辅助点。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N = 301000;
vector<int>edge[N];

map<int,vector<int>>r,c;
map<int,int>rid,cid;
map<pair<int,int>,int>id;

int dfn[N],low[N],ins[N],idx,bel[N],cnt;
stack<int>stk;
int n,R,C,dp[N],ans,x[N],y[N],ty[N];

int tot;
void dfs(int u)
{
	dfn[u] = low[u] = ++idx;
	ins[u] = true;
	stk.push(u);//还没被切掉的点
	for(auto v:edge[u])
	{
		if(!dfn[v])dfs(v);
		if(ins[v])low[u] = min(low[u],low[v]);
	}
	if(dfn[u] == low[u]){
		++cnt;
		int sz = 0;
		dp[cnt] = 0;
		while(1)
		{
			int v = stk.top();
			ins[v] = false;
			bel[v] = cnt;
			sz+=(v<=n);//注意不要把辅助点加进去了！
			stk.pop();
			for(auto w:edge[v])
			{
				if(bel[w]!=cnt&&bel[w]!=0)
				{
					dp[cnt] = max(dp[cnt],dp[bel[w]]);
				}		
			}
			if(u==v)break;
		}
		dp[cnt] += sz;
		ans  = max(ans,dp[cnt]);
	}
}
void tarjan()
{
	for(int i = 1;i<=tot;i++)
	{
		if(!dfn[i])dfs(i);
	}
}


int main()
{
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);

	cin>>n>>R>>C;
	for(int i = 1;i<=n;i++)
	{
		cin>>x[i]>>y[i]>>ty[i];
		id[{x[i],y[i]}] = i;
		r[x[i]].push_back(i);
		c[y[i]].push_back(i);
	}
	tot = n;
	for(int i  = 1;i<=n;i++)
	{
		if(ty[i]==1)
		{
			if(!rid.count(x[i]))
			{
				rid[x[i]] = ++tot;
				for(auto id:r[x[i]])edge[tot].push_back(id);
			}
			edge[i].push_back(rid[x[i]]);
		}
		else if(ty[i]==2)
		{
			if(!cid.count(y[i]))
			{
				cid[y[i]] = ++tot;
				for(auto id:c[y[i]])edge[tot].push_back(id);
			}
			edge[i].push_back(cid[y[i]]);
		}
		else if(ty[i]==3)
		{
			for(int dx = -1;dx<=1;dx++)
			{
				for(int dy = -1;dy<=1;dy++)
				{
					if(dx==0&&dy==0)continue;
					if(!id.count({x[i]+dx,y[i]+dy}))continue;
					edge[i].push_back(id[{x[i]+dx,y[i]+dy}]);
				}
			}

		}
	}
	tarjan();
	cout<<ans<<"\n";
}

标签：cnt,连通,int,图论,ins,dfn,low,dp,分量
From： https://www.cnblogs.com/nannandbk/p/17585080.html

相关文章

  • 图论选做
    P3465[POI2008]CLO-Toll[基环树][并查集][提高+/省选-]考虑依照题意，只要有一个环并且图连通，就能满足每个点在一些边定向后，都有为1的入度。即选择一些边构成一个外向基环树，就可以满足题意solution:先跑出一棵生成树找一条非树边（这样就能找到一个环），并对这个环定向然后依......
  • 为什么直流分量导致归一化频谱变小？
    直接举一个例子。假设有一个包含N个样本的信号，表示\(x[n]\)，其中\(n=0,1,2,...,N-1\)。信号的DFT表示\(X[k]\)，其中\(k=0,1,2,...,N-1\)，对应信号在不同频率上的分量，DFT的计算公式如下：\[X[k]=\sum\nolimits_{n=0}^Nx[n]\cdote^{-j(2\pi/N)\cdotk\cdotn}......
  • 7.26 day3图论
    战绩:100+100+90+25=315rk2(如果T3不挂10分就rk1了)T1正解用的是状态之间建边跑bfs，赛时我没想到状态之间建边，糊了个费用流，同样能过，思路也很简单，直接网格之间建费用为1流量无限的边，在控制点和解密点限制一下流量即可T2二分答案+最小生成树检验注意可能爆longlong要边加边判......
  • 【学习笔记】无向图的连通性
    #割点**定义：**在无向图连通图中，若把点$x$删去后整个图就不连通了，则$x$为割点（割顶）。**朴素方法：**每次删去一个点，然后判断图是否连通，时间复杂度为$O(n(n+m))$。**Tarjan算法：**$dfn_x$：$x$被`dfs`到的时间戳$low_x$：在$x$及以后被搜索的所有节点的$low$值和这些节......
  • 图论中的实用定理与结论
    结合图论中的概念与定义食用更佳。网络流与二分图Konig定理：最小点覆盖=最大匹配（proof）二分图最大独立集=点数-最大匹配二分图最大团=补图的最大独立集最大流=最小割二分图最小链覆盖数=最小边覆盖=节点数-最大匹配数有孤立点的二分图没有边覆盖Hall定......
  • Dubbo Triple 协议重磅升级：支持通过 HTTP 连通 Web 与后端微服务
    作者：刘军全新升级的Triple协议在微服务协议选型方面我们看到越来越多的应用从Dubbo2TCP二进制协议迁移到Dubbo3Triple协议(兼容gRPC)，以充分利用Triple的高效、全双工、Streaming流式通信模型等能力；Triple+HTTP/2的组合很好的解决了后端服务穿透性等问题，但在阿里及......
  • 7.20 图论笔记
    T1题目•在\(N\)个点\(P\)条边的加权无向图上求出一条从\(1\)号结点到\(N\)号结点的路径，使路径上第\(K+1\)大的边权尽量小。•\(0≤K<N≤1000\),\(1≤P≤2000\)。Solution•一道自己做出来的蓝。•二分第\(K+1\)大边权为\(mid\)，每次把边权......
  • 7.19 图论
    最小生成树[PA2014]Kuglarz\[[a,b)+[b,c)=[a,c)\]由此转化为n+1个点，只要两个点联通，就能知道有没有球，转化为最小生成树问题[国家集训队]TreeI考虑给白边加一个权重c，二分c，白边的数量因为c的变化而变化，最终一定有一种情况选了need条边，注意在边权相等时先选择白边思路题CF70......
  • 集训游记 7.19-7.20 图论
    最小生成树MSTP5994[PA2014]Kuglarz考虑连边\(i,j\)表示花费代价知道区间\([i,j)\)的奇偶性．容易发现\(i,j\)联通就可以发现表示出\([i,j)\)．考虑最终局面，一定要推出每个\([i,i+1)\)的奇偶性．要求每对\([i,i+1)\)联通．即整张图联通．最小生成树k条白边最小生成树......
  • 点双边双强连通
    点双/边双复习笔记1.点双复习割点：图中的一个点，没有这个点的话，这个图会变成两个图点双：在一个点双内，一个点到另一个点的路径有两条及以上，并且点不会走一样的注意事项：1.割点特判：son<=1且fa=x的不是割点2.环上出发特判:son=0&&fa=x的单独一个作为点双；3.看好大于等于哦！4.low[......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99