图的连通性--Tarjan算法

一些概念

无向图：

连通图：在无向图中，任意两点都直接或间接连通，则称该图为连通图。（或者说：任意两点之间都存在可到达的路径）

连通分量: G的 最大连通子图 称为G的连通分量。

有向图（ps.区别在与“强”）

强连通图：在有向图中，对于每一对顶点Vi,Vj都存在从Vi到Vj和从Vj到Vi的路径（任意两点之间都存在可到达对方的路径），则称该图为强连通图。

强连通分量： 有向图G的 最大强连通子图 称为G的强连通分量。

求强连通分量+有向图的压缩(缩点)

缩点即讲一个强连通分量中的点标记为同一类，看作一个大点包含所有其中点的信息

可以用Kosaraju但是，这里讲的是精妙的Tarjan算法

背景：dfs序

思想：做一遍DFS，用dfn[i]表示编号为i的节点在DFS过程中的访问序号(也可以叫做开始时间）用low[i]表示i节点及其下方节点所能到达的开始时间最早的节点的 开始时间 。初始时dfn[i]=low[i]

ps.大家一开始不要过于纠结low的意思，很多时候是根据需求和用途来的

important:

如果一个节点的low值等于dfn值，则说明其下方的节点不能走到其上方的节点，那么该节点u就是一个强连通分量在DFS搜索树中的根。

但是u的子孙节点未必就和u处于同一个强连通分量，怎样找出u的子孙中，哪些跟它位于同一强连通分量？

这里需要用到栈

栈的用途是保存搜过的结点并能及时删除，先上代码

int dfn[N],low[N],Time,SCC=0,Belong[N],In_du[N];

bool In_stack[N];

stack<int> st;

void Tarjan(int u) {

	dfn[u]=low[u]=++Time;

	st.push(u); In_stack[u]=true;

	for(int v=1;v<=n;v++) {

		if(mp[u][v]&&!dfn[v]) {

			Tarjan(v);

			low[u]=min(low[u],low[v]);

		}

		else if(mp[u][v]&&dfn[v]!=0&&In_stack[v]) {

			low[u]=min(low[u],dfn[v]);

		}

	}

	if(low[u]==dfn[u]) {

		++SCC; int v;

		do {

			v=st.top(); st.pop();

			In_stack[v]=false; Belong[v]=SCC;	//belong 缩点

		}while(v!=u);	//直到删除了最高点

	}

}

注意的是理解代码的In_stack[]标记，

因为如果你不可以反祖边指向了一个被遍历过且已经出栈的结点。（一个点一旦出了栈，它便有了belong)

缩点使图缩为DAG图

因此拓扑排序（图上的动态规划），在此前许会用缩点预处理

此处设一道基础例题：【APIO2009】抢掠计划

题意是：有向图中，有些点是酒吧，有的不是。每一个点都有它的价值，不过你只能抢一次并加上该价值。你从s出发到任意一个有酒吧的点结束。问您能抢到的最大价值是多少。

方程是：dp[v] = Max{ dp[u]+len[u][v]; }

为了保证无后效性：按照 Tarjan缩点，处理新图，拓扑排序中DAG动态规划/记忆化搜索 的顺序，来码题：

    #include<bits/stdc++.h>

    using namespace std;

    const int N=5e5+5;

    int head[N],to[N],tot,nxt[N],val[N],jb[N];

    int Head[N],To[N],Tot,Nxt[N],f[N];

    int Time,dfn[N],low[N],Belong[N],size[N],SCC,In[N];

    stack<int> st;

    queue<int> Q;

    bool Instack[N];

    void add_edge(int u,int v) {

    	tot++; nxt[tot]=head[u]; to[tot]=v; head[u]=tot;

    }

    void Add_edge(int u,int v) {

    	Tot++; Nxt[Tot]=Head[u]; To[Tot]=v; Head[u]=Tot;

    }

    void Tarjan(int u) {

    	dfn[u]=low[u]=++Time;

    	st.push(u); Instack[u]=true;

    	for(int i=head[u];i;i=nxt[i]) {

    		int v=to[i];

    		if(!dfn[v]) {

    			Tarjan(v);

    			low[u]=min(low[u],low[v]);

    		}

    		else if(Instack[v]) {

    			low[u]=min(low[u],dfn[v]);

    		}

    	}

    	if(dfn[u]==low[u]) {

    		SCC++; int v;

    		do {

    			v=st.top(); st.pop(); Instack[v]=false;

    			Belong[v]=SCC; size[SCC]+=val[v];

    		}while(v!=u);

    	}

    }

    int main() {

    	int n,m,s,p;

    	scanf("%d%d",&n,&m);

    	for(int i=1;i<=m;i++) {

    		int u,v;

    		scanf("%d%d",&u,&v);

    		add_edge(u,v);

    	}

    	for(int i=1;i<=n;i++) scanf("%d",&val[i]);

    	scanf("%d%d",&s,&p);

    	for(int i=1;i<=p;i++) scanf("%d",&jb[i]);

    	Tarjan(s);		//这样被缩的点(有belong的点)都能被s到达

    	for(int u=1;u<=n;u++) {

    		for(int j=head[u];j;j=nxt[j]) {

    			int v=to[j];

    			if(!Belong[u]||!Belong[v]) continue;

    			if(Belong[u]!=Belong[v]) {

    				Add_edge(Belong[u],Belong[v]); In[Belong[v]]++;

    			}

    		}

    	}

    	Q.push(Belong[s]);

    	for(int i=1;i<=SCC;i++) {

    		f[i]=size[i];

    	}

    	while(!Q.empty()) {

    		int u=Q.front(); Q.pop();

    		for(int j=Head[u];j;j=Nxt[j]) {

    			int v=To[j];

    			f[v]=max(f[v],f[u]+size[v]);

    			In[v]--; if(!In[v]) Q.push(v);

    		}

    	}

    	int ans=0;

    	for(int i=1;i<=p;i++) {

    		if(Belong[jb[i]]) {

    			ans=max(ans,f[Belong[jb[i]]]);

    		}

    	}

    	printf("%d",ans);

    	return 0;

    }

再讲一道有趣的强连通分量题目吧。

洛谷 P1407 稳定婚姻

题目大概讲了2n个点，其中有n对夫妻，又有m对情侣，请问能否在第i对夫妻离婚的情况下，所有人都能找到对象。

思路:将每对夫妻(女->男)建有向图，再将每对情侣按照（男->女）连边,【环的点数都为偶】判断每队夫妻是否在同一个一个强连通分量上,这样它们不在一起时，才能错序排列以配偶。

因此，代码：

    #include<stdio.h>

    #include<bits/stdc++.h>

    using namespace std;

    const int N=1e5+5;

    int a[N],b[N];

    int num,tot,ng,nb,head[N],nxt[N],to[N],cnt;

    int Time,dfn[N],low[N],Belong[N],SCC;

    bool Instack[N];

    stack<int> st;

    void add_edge(int u,int v) {

    	tot++; nxt[tot]=head[u]; to[tot]=v; head[u]=tot;

    }

    void Tarjan(int u) {

    	dfn[u]=low[u]=++Time;

    	st.push(u); Instack[u]=true;

    	for(int i=head[u];i;i=nxt[i]) {

    		int v=to[i];

    		if(!dfn[v]) {

    			Tarjan(v);

    			low[u]=min(low[u],low[v]);

    		}

    		else if(Instack[v]) {

    			low[u]=min(low[u],dfn[v]);

    		}

    	}

    	if(dfn[u]==low[u]) {

    		SCC++; int v;

    		do {

    			v=st.top(); st.pop(); Instack[v]=false;

    			Belong[v]=SCC;

    		}while(v!=u);

    	}

    }

    map<string,int> mp;

    int main() {

    	int n,m;

    	scanf("%d",&n);

    	for(int i=1;i<=n;i++) {

    		string p,q;

    		cin>>p>>q;

    		mp[p]=++num;

    		mp[q]=++num;

    		a[i]=mp[p]; b[i]=mp[q];

    		add_edge(a[i],b[i]);

    	}

    	scanf("%d",&m);

    	for(int i=1;i<=m;i++) {

    		string p,q;

    		cin>>p>>q;

    		int u=mp[p],v=mp[q];

    		add_edge(v,u);

    	}

    	for(int i=1;i<=n*2;i++) {

    		if(!dfn[i]) {

    			Tarjan(i);

    		}

    	}

    	for(int i=1;i<=n;i++) {

    		if(Belong[a[i]]!=Belong[b[i]]) {

    			printf("Safe\n");

    		}

    		else printf("Unsafe\n");

    	}

    	return 0;

    }

巴特西

图的连通性--Tarjan算法

无向图：

有向图（ps.区别在与“强”）

最新文章

热门文章

巴特西

图的连通性--Tarjan算法

无向图：

有向图 （ps.区别在与“强”）

最新文章

热门文章

有向图（ps.区别在与“强”）