有向图和无向图的连通性学习小记 Poj 1269 迷宫城堡

ゞ浴缸里的玫瑰 2022-10-30 15:26 127阅读 0赞

2014-7-30 更新

# 学习资料 #

[有向图的强连通分量入门][Link 1]

[有向图强连通分量的Tarjan算法 - BYVoid][Tarjan_ - BYVoid]

[强连通分支、桥和割点][Link 2]

[图的割点、桥与双连通分支 - BYVoid][- BYVoid]

# 知识点小记 #

一些定理：

1. 有向无环图中唯一出度为0的点，一定可以由任何点出发均可达(由于无环，所以从任何点出发往前走，必然终止于一个出度为0的点)

2. 有向无环图中所有入度不为0的点，一定可以由某个入度为0的点出发可达。(由于无环，所以从任何入度不为0的点往回走，必然终止于一个入度为0的点)

3. 一个点u是割点，当且仅当满足(1)或(2)

(1) u为树根，且u有多于一个子树。

(2) u不为树根，且满足存在(u,v)为树枝边(或称父子边，即u为v在搜索树中的父亲)，使得dfn(u)<=low(v)。

4. 一条无向边(u,v)是桥，当且仅当(u,v)为树枝边，且满足dfn(u)<low(v)（前提是其没有重边）。

无向连通图点双连通分支 ： 不包含割点的极大连通子图

无向连通图边双连通分支 ： 不包含桥的极大连通子图

举例：如图，所有边均为无向边

![SouthEast][]

由于去掉任意一条边原图都是连通的，所以原图整体是边双连通的，但3是一个割点，如果去掉3原图就不连通了，所以原图整体不是点双连通的。

重边和自环的影响：

自环指含有连向自己的边。

有向图：只有一种强连通，重边和自环对于强连通都没有任何影响。

无向图：双连通分为点双连通和边双连通

自环对于两种双连通没有任何影响

重边对点双连通没有影响，但是对于边双连通有影响，因为在求边双连通时，要求对于任意两点至少存在两条“边不重复”的路径。

# 还没做的题目 #

Hdu 3844 求点双连通分量

Poj 3352 加边做双连通图

Poj 1523 无向图求割点及去除割点后产生的块数

[POJ1904/ZOJ2470 King's Quest（tarjan判强连通分量） - laoda扯一扯][POJ1904_ZOJ2470 King_s Quest_tarjan_ - laoda]

[HDU 4685 二分图匹配+tarjan][HDU 4685 _tarjan]

Poj 3694 结合LCA

Poj 2942 涉及奇环

Poj 3592 缩点+最长路

# 强连通模板 #

同时适用于无向图求割点

#include <cstdio>
    #include <cstring>
    #include <stack>
    #define min(x,y) ((x)<(y)?(x):(y))
    #define max(x,y) ((x)>(y)?(x):(y))
    using namespace std;
    
    const int INF=0x3f3f3f3f;
    
    const int nPoint=1010;   //原节点数
    const int nEdges=30005;  //原边数
    const int nNewmap=1005;  //新图最大节点数
    
    class SCC // strongly connected components
    {//节点标号从1开始
    private:
    	struct Edge
    	{
    		int v,next;
    	}edges[nEdges];
    
    	int dfn[nPoint],low[nPoint],head[nPoint];//dfn(u)为节点u搜索的次序编号(时间戳),low(u)为u或u的子树能够追溯到的最早的栈中节点的次序号
    	bool visit[nPoint];   //标记是否在栈中
    	int in[nPoint],out[nPoint],color[nPoint];   //color[]保存各强连通分量包含的节点数,in[]各强连通分量的入度,out[]各强连通分量的出度
    	int belong[nPoint];             //每个结点所对应的强连通分量标号数组
    	bool DAG[nNewmap][nNewmap];      //存储缩点之后的新图,有向无环图DAG
    	int n,e,id,colornum;         //colornum强连通分量的个数
    	int nIn_0,nOut_0;        //nIn_0=0入度为0的点的个数,nOut_0=0出度为0的点个数
    	stack<int> S;
    
    	int cnt[nPoint];   //存储割点被切掉后会新分出的块数,可用来统计割点个数(不为0即为割点)
    
    	void DFS (int u)
    	{
    		int i,top,v;
    		dfn[u]=low[u]=++id;  //id为时间戳
    		S.push(u);
    		visit[u]=true;
    		for (i=head[u];i!=-1;i=edges[i].next)
    		{
    			v=edges[i].v;
    			if (dfn[v]==0)
    			{//未被访问
    				DFS(v);//继续向下找
    				if (low[v]>=dfn[u])  //是割点,统计
    					cnt[u]++;
    				low[u]=min(low[u],low[v]);//更新u节点所能到达的最小层数
    			}
    			else if (visit[v])
    				low[u]=min(low[u],dfn[v]);
    		}
    		if (dfn[u]<=low[u])   //  ==
    		{//如果节点u是强连通分量的根
    			colornum++;   //连通分量标号+1
    			do
    			{
    				top=S.top(); //
    				S.pop();
    				visit[top]=false;
    				belong[top]=colornum; //出栈节点top属于colornum标号的强连通分量
    				color[colornum]++;
    			}while (top!=u);  //直接将u从栈中退出
    		}
    	}
    
    public:
    
    	void Init (int _n)
    	{
    		n=_n;
    		id=colornum=e=0;
    		nIn_0=nOut_0=0;
    		memset(head,-1,sizeof(head));
    		memset(visit,false,sizeof(visit));
    		memset(dfn,0,sizeof(dfn));
    		memset(in,0,sizeof(in));
    		memset(out,0,sizeof(out));
    		memset(cnt,0,sizeof(cnt));
    	}
    	
    	void Add (int u,int v)
    	{
    		edges[e].v=v;
    		edges[e].next=head[u];
    		head[u]=e++;
    	}
    	
    	int Tarjan ()  //返回强连通分量的个数
    	{
    		while (!S.empty())   //清空栈
    			S.pop();
    		
    		for (int i=1;i<=n;i++)  //枚举每个节点,搜索连通分量
    			if (!dfn[i])   //未被访问
    			{
    				DFS(i);   //则找该节点的连通分量
    				/*不可以在这里计算colornum,例对于5个节点的有向图,边
    				1 2,1 4,1 3,2 4,2 5,5 1会返回错误结果 1个 */
    				cnt[i]--;   //原来本身有一块
    			}
    		return colornum;
    	}
    	
    	void Cal ()    //计算in[],out[],nOut_0,nIn_0
    	{//与TopoOrder ()同时调则无法正确计算 in 数组(重复使用)
    		int i,j;
    		Tarjan();
    		for (i=1;i<=n;i++)
    			for (j=head[i];j!=-1;j=edges[j].next)
    				if (belong[i]!=belong[edges[j].v])
    				{
    					in[belong[edges[j].v]]++;
    					out[belong[i]]++;
    				}
    		for (i=1;i<=colornum;i++)
    		{
    			nOut_0+=!out[i];
    			nIn_0+=!in[i];
    		}
    	}
    
    	void Build ()       //建立新图DAG
    	{
    		memset(DAG,0,sizeof(DAG));
    		for (int i=1;i<=n;i++)
    			for (int j=head[i];j!=-1;j=edges[j].next)
    				if (belong[i]!=belong[edges[j].v])
    					DAG[belong[i]] [belong[edges[j].v]] =true;
    	}
    
    	bool TopoOrder ()  //拓扑排序,返回是否有分叉
    	{//既是否为一条链
    		int i,j;
    		for (i=1;i<=colornum;i++)
    			for (j=1;j<=colornum;j++)
    				if (DAG[i][j]) in[j]++;
    		for (i=1;i<colornum;i++)
    		{
    			int cnt=0;  //分支条数
    			int p=0;  //下一节点
    			for (j=1;j<=colornum && cnt<=1;j++)
    				if (in[j]==0)
    					cnt++,p=j;
    			if (cnt>1) return false;
    			for (j=1;j<=colornum;j++)
    				if (DAG[p][j]) in[j]--;
    			in[p]=INF;
    		}
    		return true;
    	}
    
    	void Deal ()
    	{//计算割点数目
    		Tarjan ();
    		int k=0;
    		for (int i=1;i<=n;i++)
    			if (cnt[i])
    				k++;
    		printf("%d\n",k);
    	}
    }ob;
    
    int main ()  
    { 
    #ifdef ONLINE_JUDGE
    #else
    	freopen("read.txt","r",stdin);
    #endif 
    	int n,u,v;  
    	while (scanf("%d",&n),n)  
    	{
    		ob.Init (n);  
    		while (scanf("%d",&u),u) while (getchar()!='\n')  
    		{  
    			scanf("%d",&v);  
    			ob.Add(u,v);  
    			ob.Add(v,u);  
    		}  
    		ob.Deal ();
    	}  
    	return 0;  
    }

# 双连通模板 #

可以求桥，缩点，可用于有重边

其他写法可以参考 [边双连通模版 - 九野的博客][-]

#pragma comment(linker, "/STACK:1024000000,1024000000")
    #include <cstdio>
    #include <cstring>
    #include <stack>
    #include <queue>
    #include <vector>
    #define min(x,y) ((x)<(y)?(x):(y))
    #define max(x,y) ((x)>(y)?(x):(y))
    using namespace std;
    
    const int INF=0x3f3f3f3f;
    
    const int nPoint=200010;
    const int nEdges=2000010;
    vector<int>G[nPoint];
    
    class BCC
    {
    public:
    	struct Edge{
    		int from, to, next;
    		bool cut;  //是否为桥
    	}edge[nEdges];
    
    	int e,id,n;
    	int head[nPoint],dfn[nPoint], low[nPoint];
    	int colornum, top; //双连通分量数,栈顶
    	int color[nPoint],Stack[nPoint];
    	bool iscut[nPoint];  //该点是否为割点
    	int bri_cut;    //桥的数目
    
    	void Add (int u, int v){
    		Edge E={u,v,head[u],false};
    		edge[ e ] = E;
    		head[u] = e++;
    	}
    
    	void Tarjan (int u, int pre)
    	{
    		dfn[u]=low[u]=++id;
    		Stack[++top]=u;
    		int child=0, flag=1;
    		
    		for (int i=head[u]; ~i; i=edge[i].next)
    		{
    			int v=edge[i].to;
    			//if (v == pre) continue; //重边算一条的写法
    			if (flag && v==pre)
    			{//重边有效的写法
    				flag = 0; 
    				continue;
    			}
    			if (!dfn[v])
    			{
    				child++;
    				Tarjan(v,u);
    				low[u] = min(low[u], low[v]);
    				if (low[v] >= dfn[u])
    				{
    					iscut[u] = true;  //是割点
    					if (low[v]>dfn[u])
    						edge[i].cut = edge[i^1].cut = true;  //是桥
    				}
    			}
    			else low[u] = min(low[u], dfn[v]);
    		}
    		if (child == 1 && pre<0) //树根
    			iscut[u] = false;
    		if (low[u] == dfn[u])
    		{
    			colornum++;
    			do
    			{
    				color[ Stack[top] ] = colornum;
    			}while(Stack[top--] != u);
    		}
    	}
    
    	void Init (int _n)
    	{
    		n=_n;
    		memset(head, -1, sizeof(head));
    		memset(dfn, 0, sizeof(dfn));
    		memset(iscut, 0, sizeof(iscut));
    		memset(color, -1, sizeof(color));
    		bri_cut=e=id= 0;
    		top = colornum = 0;
    	}
    
    	void Deal ()
    	{
    		int i;
    		for (i=1; i<=n; i++) if (!dfn[i])
    			Tarjan(i, -1);
    		for (i=0; i<=colornum; i++)
    			G[i].clear();
    		for (i=0; i<e; i+=2)
    		{//建新图
    			int u = color[edge[i].from];
    			int v = color[edge[i].to];
    			if (u != v)
    				G[u].push_back(v), G[v].push_back(u);
    			bri_cut += edge[i].cut;
    		}
    	}
    }ob;
    
    int n,m;
    
    int main ()
    {
    #ifdef ONLINE_JUDGE
    #else
    	freopen("read.txt","r",stdin);
    #endif
    	while (scanf("%d%d",&n,&m), m+n)
    	{
    		ob.Init(n);
    		int u,v;
    		while (m--)
    		{
    			scanf("%d %d",&u,&v);
    			ob.Add(u,v);
    			ob.Add(v,u);
    		}
    		ob.Deal();
    	}
    	return 0;
    }

# Poj 1269 #

#include <cstdio>
    #include <cstring>
    #include <stack>
    #define min(x,y) ((x)<(y)?(x):(y))
    #define max(x,y) ((x)>(y)?(x):(y))
    using namespace std;
    
    const int nPoint=10005;
    const int nEdges=100005;
    
    class Qiangliantong
    {
    private:
    	struct Edge
    	{
    		int v,next;
    	}edges[nEdges];
    
    	int dfn[nPoint],low[nPoint],head[nPoint];
    	bool visit[nPoint];   //标记是否在栈中
    	int in[nPoint],out[nPoint],color[nPoint];   //color[]保存各强连通分量包含的节点数,in[]各强连通分量的入度,out[]各强连通分量的出度
    	int DAG[nPoint];             //储存新图,有向无环图DAG,也即每个结点所对应的强连通分量标号数组
    	int n,e,id,colornum;         //colornum强连通分量的个数
    	int nIn_0,nOut_0;        //nIn_0=0入度为0的点的个数,nOut_0=0出度为0的点个数
    	stack<int> S;
    
    	void DFS (int u)
    	{
    		int i,top,v;
    		dfn[u]=low[u]=++id;  //id为时间戳
    		S.push(u);
    		visit[u]=true;
    		for (i=head[u];i!=-1;i=edges[i].next)
    		{
    			v=edges[i].v;
    			if (!dfn[v])
    			{//未被访问
    				DFS(v);//继续向下找
    				low[u]=min(low[u],low[v]);//更新u节点所能到达的最小层数
    			}
    			else if (visit[v])
    				low[u]=min(low[u],dfn[v]);
    		}
    		if (dfn[u]<=low[u])   //  ==
    		{//如果节点v是强连通分量的根
    			colornum++;   //连通分量标号+1
    			do
    			{
    				top=S.top(); //
    				S.pop();
    				visit[top]=false;
    				DAG[top]=colornum; //出栈节点top属于colornum标号的强连通分量
    				color[colornum]++;
    			}while (top!=u);  //直接将u从栈中退出
    		}
    	}
    
    public:
    
    	void Init (int _n)
    	{
    		n=_n;
    		id=colornum=e=0;
    		nIn_0=nOut_0=0;
    		memset(head,-1,sizeof(head));
    		memset(visit,false,sizeof(visit));
    		memset(dfn,0,sizeof(dfn));
    		memset(in,0,sizeof(in));
    		memset(out,0,sizeof(out));
    	}
    	
    	void Add (int u,int v)
    	{
    		edges[e].v=v;
    		edges[e].next=head[u];
    		head[u]=e++;
    	}
    	
    	int Tarjan ()  //返回强连通分量的个数
    	{
    		int i;	
    		while (!S.empty())   //清空栈
    			S.pop();
    		for (i=1;i<=n;i++)  //枚举每个节点,搜索连通分量
    			if (!dfn[i])   //未被访问
    				DFS(i);   //则找该节点的连通分量
    		return colornum;
    	}
    	
    	void Cal ()    //计算in[],out[],nOut_0,nIn_0
    	{
    		int i,j;
    		Tarjan();
    		for (i=1;i<=n;i++)
    			for (j=head[i];j!=-1;j=edges[j].next)
    				if (DAG[i]!=DAG[edges[j].v])
    				{
    					in[DAG[edges[j].v]]++;
    					out[DAG[i]]++;
    				}
    		for (i=1;i<=colornum;i++)
    		{
    			nOut_0+=!out[i];
    			nIn_0+=!in[i];
    		}
    	}
    }ob;
    
    int main ()
    {
    	int n,m;
    	while (scanf("%d%d",&n,&m),n || m)
    	{
    		ob.Init (n);
    		while (m--)
    		{
    			int u, v;
    			scanf("%d%d",&u,&v);
    			ob.Add(u,v);
    		}
            ;
    		if (ob.Tarjan() == 1)
    			printf("Yes\n");  //只有一个强连通分量，说明此图各个结点都可达
    		else printf("No\n");
    	}
    	return 0;
    }

[Link 1]: http://wenku.baidu.com/link?url=Vgpd1g7wUMPrb3128ifFMHrPWmW0Iyif6MjmSVdvMxRvzzj5YdtUO1NCMRahc86DYvq4dvfRouSIjDAlfuLOr2obgMr7ioUlR3TdaO0dYAa
[Tarjan_ - BYVoid]: https://www.byvoid.com/blog/scc-tarjan/
[Link 2]: http://wenku.baidu.com/view/ee8160f8770bf78a652954ad.html?re=view
[- BYVoid]: https://www.byvoid.com/blog/biconnect/
[SouthEast]: /images/20221024/86df4048fb9b4e49b0fb29726412faf6.png
[POJ1904_ZOJ2470 King_s Quest_tarjan_ - laoda]: http://blog.csdn.net/l04205613/article/details/6654820
[HDU 4685 _tarjan]: http://blog.csdn.net/sdj222555/article/details/9990131
[-]: http://blog.csdn.net/qq574857122/article/details/11712551