为您推荐:
精华内容
最热下载
问答
  • 5星
    842KB weixin_38037403 2021-08-26 17:48:03
  • 5星
    25.85MB qq_19388797 2021-09-09 16:13:52
  • 5星
    135.91MB qq_34351067 2021-04-16 14:11:28
  • 5星
    52.11MB weixin_41581125 2021-01-06 14:22:37
  • 5星
    103KB yifeng16888 2021-07-30 16:07:56
  • 5星
    40KB weixin_51194902 2021-01-08 12:19:19
  • 5星
    49.33MB weixin_38950816 2021-04-28 18:55:32
  • 5星
    923.93MB weixin_37932346 2021-04-23 20:19:48
  • 5星
    148KB xiaoge_586 2021-02-24 19:53:35
  • 5星
    4.68MB Mrcomj 2021-06-07 19:41:12
  • 无向图割点割边无向图割点割边练习题P3388 【模板】割点(割顶)397. 逃不掉的路 无向图割点割边 点双联通分量vcc:分量中没有割点,每条边属于1个点双 边双联通分量ecc:分量中没有割边,每个点属于1个边双 边双 ...

    无向图割点割边

    割点:无向连通图中,如果删除某点后,图变成不连通,则称该点为割点
    割边:无向连通图中,如果删除某边后,图变成不连通,则称该边为割边

    边双:边双联通分量ecc:分量中没有割边,每个点属于1个边双
    点双:点双联通分量vcc:分量中没有割点,每条边属于1个点双,割点属于多个点双

    算法

    • 顶点 u 是割点只需满足以下两个条件中的其中一个:
      (1)特判树根: u 为树根,且 u 有至少两个子树 。(无向连通图不存在C边,只存在T边和B边,即只存在祖先关系,包括父子关系)
      (2)u 不为树根:在DFS树上u有子节点v,且满足 d f n [ u ] ≤ l o w [ v ] dfn[u]\le low[v] dfn[u]low[v]。(意思是说 v 通过 B 边最多只能回到 u)

    • 边(u,v)是不是割边,当且仅当(u,v)为树边,且满足 d f n [ u ] < l o w [ v ] dfn[u]<low[v] dfn[u]<low[v]。(意思是说 v 通过 B 边不能回到 u 及其祖先)
      注意:非树边不能是割边,重边不能是割边。构成了一个环,那么就构成一个边双了

    • 点双和边双都是大环,只不过点双多了一个类型:两个点相连。

    边双

    • 找到所有的割边后删去 -> 剩下的就是边双联通分量
    • 边双 + 割边 = 树
    • 两个点必经边数,即树上两点之间的距离

    建图过程
    (1) dfs1:找到所有的割边
    (2) dfs2:每个联通块内不通过割边记为同一个ecc
    (3)然后遍历原图所有边

    点双

    • 利用圆方树建图
    • 两点必经点数,即树上距离/2
    • 两边必经点数,即两边所在方点之间必经的点数

    建图过程

    参考链接

    练习题

    P3388 【模板】割点(割顶)

    题意:给出一个 n 个点 m 条边的无向图,求图的割点

    #include <bits/stdc++.h>
    #define ll long long
    using namespace std;
    const int maxn=2e4+10,maxm=1e5+10;
    
    int n,m;
    vector<int> e[maxn];
    map<int,int> mp[maxn];
    
    int dfn[maxn],low[maxn],times=0;
    int iscp[maxn],isce[maxn],fa[maxn],rt;
    
    void dfs(int u)
    {
    	dfn[u]=low[u]=++times;
    	for(auto v: e[u])
    	{
    		if(!dfn[v])
    		{
    			fa[v]=u;
    			dfs(v);
    			low[u]=min(low[u],low[v]);
    			if(dfn[u]<low[v]&&mp[u][v]<=1&&mp[v][u]<=1) isce[v]=1;
    			if(dfn[u]<=low[v]&&u!=rt) iscp[u]=1;
    		}
    		else if(v!=fa[u]) low[u]=min(low[u],dfn[v]);
    	}
    }
    
    int main()
    {
    	scanf("%d%d",&n,&m);
    	for(int i=1;i<=m;++i)
    	{
    		int u,v;
    		scanf("%d%d",&u,&v);
    		e[u].push_back(v);
    		e[v].push_back(u);
    		if(u>v) swap(u,v);
    		mp[u][v]++;
    	}
    	//特判根 
    	for(int i=1;i<=n;++i)
    	{
    		if(!dfn[i])
    		{
    			rt=i;
    			dfs(i);
    			int cnt=0;
    			for(auto v: e[rt])
    				if(fa[v]==rt) ++cnt;
    			iscp[rt]=(cnt>1);
    		}
    	}
    	int ans=0;
    	for(int i=1;i<=n;++i)
    		if(iscp[i]) ans++;
    	printf("%d\n",ans);
    	for(int i=1;i<=n;++i)
    		if(iscp[i]) printf("%d ",i);
    	puts("");
    	return 0;
    }
    
    #include <bits/stdc++.h>
    #define ll long long
    using namespace std;
    const int maxn=2e4+10,maxm=1e5+10;
    
    int n,m;
    vector<int> e[maxn];
    map<int,int> mp[maxn];
    
    int dfn[maxn],low[maxn],times=0;
    int iscp[maxn],isce[maxn],fa[maxn],rt;
    
    void dfs(int u)
    {
    	dfn[u]=low[u]=++times;
    	int cnt=0;
    	for(auto v: e[u])
    	{
    		if(!dfn[v])
    		{
    			fa[v]=u;
    			dfs(v);
    			low[u]=min(low[u],low[v]);
    			if(dfn[u]<low[v]&&mp[u][v]<=1&&mp[v][u]<=1) isce[v]=1;
    			if(dfn[u]<=low[v])
    			{
    				cnt++;
    				if(u!=rt||cnt>1) iscp[u]=1;
    			}
    		}
    		else if(v!=fa[u]) low[u]=min(low[u],dfn[v]);
    	}
    }
    
    int main()
    {
    	scanf("%d%d",&n,&m);
    	for(int i=1;i<=m;++i)
    	{
    		int u,v;
    		scanf("%d%d",&u,&v);
    		e[u].push_back(v);
    		e[v].push_back(u);
    		if(u>v) swap(u,v);
    		mp[u][v]++;
    	}
    	for(int i=1;i<=n;++i)
    		if(!dfn[i]) rt=i,dfs(i);
    	int ans=0;
    	for(int i=1;i<=n;++i)
    		if(iscp[i]) ans++;
    	printf("%d\n",ans);
    	for(int i=1;i<=n;++i)
    		if(iscp[i]) printf("%d ",i);
    	puts("");
    	return 0;
    }
    

    397. 逃不掉的路

    题意:给定一个无自环、无重边的无向连通图。询问 ( u , v ) (u,v) (u,v) 之间有多少座桥,询问 q 次
    思路:边双缩点后变成一棵树,每一条边就是一座桥,然后就是询问 ( u , v ) (u,v) (u,v) 之间边的数量,直接 lca 即可。

    #include <bits/stdc++.h>
    #define ll long long
    using namespace std;
    const int maxn=1e5+10;
    
    int n,m,q;
    vector<int> e[maxn],e2[maxn];
    
    int dfn[maxn],low[maxn],times=0;
    int fa2[maxn],isce[maxn];
    
    void dfs1(int u)
    {
    	dfn[u]=low[u]=++times;
    	for(auto v: e[u])
    	{
    		if(!dfn[v])
    		{
    			fa2[v]=u;
    			dfs1(v);
    			low[u]=min(low[u],low[v]);
    			if(dfn[u]<low[v]) isce[v]=1;
    		}
    		else if(v!=fa2[u]) low[u]=min(low[u],dfn[v]);
    	}
    }
    int ecc[maxn],ecnt=0;
    void dfs2(int u)
    {
    	ecc[u]=ecnt;
    	for(auto v: e[u])
    	{
    		if(ecc[v]||fa2[v]==u&&isce[v]||v==fa2[u]&&isce[u]) continue;
    		dfs2(v);
    	}
    }
    int fa[maxn][21],depth[maxn];
    void dfs3(int u,int f=0)
    {
    	fa[u][0]=f;
    	for(int i=1;i<=20;++i)
    		fa[u][i]=fa[fa[u][i-1]][i-1];
    	for(auto v: e2[u])
    	{
    		if(v==f) continue;
    		depth[v]=depth[u]+1;
    		dfs3(v,u);
    	}
    }
    int lca(int u,int v)
    {
    	if(depth[u]>depth[v]) swap(u,v);
    	int dis=depth[v]-depth[u];
    	for(int i=0;(1<<i)<=dis;++i)
    		if(dis>>i&1) v=fa[v][i];
    	if(u==v) return v;
    	for(int i=20;i>=0;--i)
    		if(fa[u][i]!=fa[v][i])
    			u=fa[u][i],v=fa[v][i];
    	return fa[u][0];
    }
    int getdis(int u,int v)
    {
    	return depth[u]+depth[v]-2*depth[lca(u,v)];
    }
    int main()
    {
    	scanf("%d%d",&n,&m);
    	for(int i=1;i<=m;++i)
    	{
    		int u,v;
    		scanf("%d%d",&u,&v);
    		e[u].push_back(v);
    		e[v].push_back(u);
    	}
    	dfs1(1);
    	
    	for(int i=1;i<=n;++i)
    		if(!ecc[i]) ecnt++,dfs2(i);
    	
    	for(int u=1;u<=n;++u)
    		for(auto v: e[u])
    			if(ecc[v]!=ecc[u])
    				e2[ecc[u]].push_back(ecc[v]);
    	dfs3(1);
    	scanf("%d",&q);
    	while(q--)
    	{
    		int u,v;
    		scanf("%d%d",&u,&v);
    		printf("%d\n",getdis(ecc[u],ecc[v]));
    	}
    	return 0;
    }
    

    364. 网络

    链接:https://www.acwing.com/problem/content/description/366/

    题意:给定一张N个点M条边的无向连通图,然后执行Q次操作,每次向图中添加一条边,并且询问当前无向图中“桥”的数量

    思路

    • 首先用边双缩点成树。
    • 每次加边时,(u,v)路径的桥就不存在了,因此暴力修改 (u,v)路径上的割边
    • 可以用并查集来加速修改,把(u,v)路径上的所有点的 fa 都设为 lca ( u , v ) 这样路径上就可以加速了
    #include <bits/stdc++.h>
    #define ll long long
    using namespace std;
    const int maxn=1e5+10;
    
    int n,m,ans;
    vector<int> e[maxn];
    map<int,int> mp[maxn];
    int dfn[maxn],low[maxn],times;
    int isce[maxn];
    int depth[maxn],fa[maxn];
    
    void dfs(int u)
    {
    	dfn[u]=low[u]=++times;
    	for(auto v: e[u])
    	{
    		if(!dfn[v])
    		{
    			fa[v]=u;
    			depth[v]=depth[u]+1;
    			dfs(v);
    			low[u]=min(low[u],low[v]);
    			if(dfn[u]<low[v]&&mp[u][v]<=1&&mp[v][u]<=1) ans++,isce[v]=1;
    		}
    		else if(v!=fa[u]) low[u]=min(low[u],dfn[v]);
    	}
    }
    
    void lca(int u,int v)
    {
    	vector<int> vec;
    	if(depth[u]<depth[v]) swap(u,v);
    	while(depth[u]>depth[v])
    	{
    		if(isce[u]) ans--,isce[u]=0;
    		vec.push_back(u);		
    		u=fa[u];	
    	}
    	while(u!=v)
    	{
    		if(isce[u]) ans--,isce[u]=0;
    		if(isce[v]) ans--,isce[v]=0;
    		vec.push_back(u);
    		vec.push_back(v);
    		u=fa[u],v=fa[v];
    	}
    	for(auto x: vec) fa[x]=u;
    }
    
    int main()
    {
        int Case=0;
    	while(scanf("%d%d",&n,&m)&&(n||m))
    	{
    		times=ans=0;	
    		for(int i=1;i<=n;++i)
    		{
    			dfn[i]=low[i]=depth[i]=fa[i]=isce[i]=0;
    			e[i].clear();
    			mp[i].clear();
    		}
    			
    		for(int i=1;i<=m;++i)
    		{
    			int u,v;
    			scanf("%d%d",&u,&v);
    			e[u].push_back(v);
    			e[v].push_back(u);
    			if(u>v) swap(u,v);
    			mp[u][v]++;
    		}
    		fa[1]=1;		
    		dfs(1);
    		
    		printf("Case %d:\n",++Case);
    		int q,u,v;
    		scanf("%d",&q);
    		while(q--)
    		{
    			scanf("%d%d",&u,&v);
    			lca(u,v);
    			printf("%d\n",ans);
    		}	
    		printf("\n");
    	}	
    	return 0;
    }
    

    395. 冗余路径

    链接:https://www.acwing.com/problem/content/397/

    题意:一个图,增加多少条边,使得能成为一个边双连通图。

    思路:边双缩点,ans = ceil(叶子数量/2)

    #include <bits/stdc++.h>
    #define ll long long
    using namespace std;
    const int maxn=5000+10;
    
    int n,m; 
    vector<int> e[maxn];
    map<int,int> mp[maxn];
    int dfn[maxn],low[maxn],times=0;
    int fa[maxn],isce[maxn];
    
    void dfs1(int u)
    {
    	dfn[u]=low[u]=++times;
    	for(auto v: e[u])
    	{
    		if(!dfn[v])
    		{
    			fa[v]=u;
    			dfs1(v);
    			low[u]=min(low[u],low[v]);
    			if(dfn[u]<low[v]&&mp[u][v]<=1&&mp[v][u]<=1) isce[v]=1;
    		}
    		else if(v!=fa[u]) low[u]=min(low[u],dfn[v]);
    	}
    }
    int ecc[maxn],ecnt=0;
    void dfs2(int u)
    {
    	ecc[u]=ecnt;
    	for(auto v: e[u])
    	{
    		if(ecc[v]||v==fa[u]&&isce[u]||u==fa[v]&&isce[v]) continue;
    		dfs2(v);
    	}
    }
    int in[maxn];
    int main()
    {
    	scanf("%d%d",&n,&m);
    	for(int i=1;i<=m;++i)
    	{
    		int u,v;
    		scanf("%d%d",&u,&v);
    		e[u].push_back(v);
    		e[v].push_back(u);
    		if(u>v) swap(u,v);
    		mp[u][v]++;
    	}
    	for(int i=1;i<=n;++i)
    		if(!dfn[i]) dfs1(i);
    	
    	for(int i=1;i<=n;++i)
    		if(!ecc[i]) ++ecnt,dfs2(i);
    	
    	for(int u=1;u<=n;++u)
    		for(auto v: e[u])
    			if(ecc[v]!=ecc[u])
    				in[ecc[v]]++;
    	int ans=0;
    	for(int i=1;i<=ecnt;++i)
    		if(in[i]==1) ans++;
    	printf("%d\n",(ans+1)/2);
    	return 0;
    }
    

    P5058 [ZJOI2004]嗅探器

    链接:https://www.luogu.com.cn/problem/P5058

    题意:给定一个无向图,问从 s 到 t 中必经的下标的最小的点是多少

    思路

    • 可以以 s 为起点建圆方树,那么就可以判断 s 、t 是否连通。
    • 如果连通,那么就从 s 开始往 t 走记录路径上经过的割点的最小值。
    • 割点判断: u 小于等于 n 且度数大于 1 。
    #include <bits/stdc++.h>
    #define ll long long
    using namespace std;
    const int maxn=2e5+10;
    
    int n,s,t;
    vector<int> e[maxn],e2[maxn<<1];
    
    int dfn[maxn],low[maxn],times=0;
    int sta[maxn],top=0,fa[maxn];
    int vcnt;
    
    void dfs1(int u)
    {
    	dfn[u]=low[u]=++times;
    	sta[++top]=u;
    	for(auto v: e[u])
    	{
    		if(!dfn[v])
    		{
    			fa[v]=u;
    			dfs1(v);
    			low[u]=min(low[u],low[v]);
    			if(dfn[u]<=low[v]) 
    			{
    				vcnt++;
    				while(1)
    				{
    					int x=sta[top--];
    					e2[vcnt].push_back(x);
    					e2[x].push_back(vcnt);
    					if(x==v) break;	
    				}
    				e2[vcnt].push_back(u);
    				e2[u].push_back(vcnt);
    			}
    		}
    		else if(v!=fa[u]) low[u]=min(low[u],dfn[v]);
    	}
    }
    //int ans=1e9;
    //void dfs2(int u,int fa)
    //{
    //	if(u==t)
    //	{
    //		if(ans==1e9) puts("No solution");
    //		else printf("%d\n",ans);
    //		exit(0);
    //	}
    //	if(u!=s&&e2[u].size()>1&&u<=n) ans=min(ans,u);
    //	for(auto v: e2[u])
    //	{
    //		if(v==fa) continue;
    //		dfs2(v,u);
    //	}
    //}
    void dfs2(int u,int ans,int fa)
    {
    	if(u==t)
    	{
    		if(ans==0) puts("No solution");
    		else printf("%d\n",ans);
    		exit(0);
    	}
    	if(u!=s&&e2[u].size()>1&&u<=n) 
    	{
    		if(ans==0) ans=u;
    		else ans=min(ans,u);
    	}
    	for(auto v: e2[u])
    	{
    		if(v==fa) continue;
    		dfs2(v,ans,u);
    	}
    }
    
    int main()
    {
    	scanf("%d",&n);
    	int u,v;
    	while(scanf("%d%d",&u,&v)&&(u||v))
    		e[u].push_back(v),e[v].push_back(u);
    	scanf("%d%d",&s,&t);
    	vcnt=n;
    	dfs1(s);
    	if(dfn[t]==0)
    	{
    		puts("No solution");
    		return 0;
    	}
    	dfs2(s,0,0);	 
    	return 0;
    }
    

    398. 交通实时查询系统

    链接:https://www.acwing.com/problem/content/description/400/

    题意:给定一个无向图,多次询问一条边到另一条边的必经点

    思路:需要知道一条边属于哪个点双vcc,dfs时把遍历到的边压栈,找到1个点双(low[v]>=dfn[u])时,弹栈直到 u->v 这条边。

    #include <bits/stdc++.h>
    #define ll long long
    using namespace std;
    const int maxn=1e5+10,maxm=1e6+10;
    
    int n,m;
    vector<pair<int,int> > e[maxn];
    vector<int> e2[maxn<<1];
    
    int dfn[maxn],low[maxn],times;
    int sta[maxn],top=0,sta2[maxm],top2=0;
    int vcnt;
    int fa[maxn],fa_id[maxn],vcc[maxm];
    
    void dfs1(int u)
    {
    	dfn[u]=low[u]=++times;
    	sta[++top]=u;
    	for(auto x: e[u])
    	{
    		int v=x.first,id=x.second;
    		if(!dfn[v])
    		{
    			fa[v]=u;
    			fa_id[v]=id;
    			sta2[++top2]=id;
    			dfs1(v);
    			low[u]=min(low[u],low[v]);
    			if(dfn[u]<=low[v])
    			{
    				vcnt++;
    				while(1)
    				{
    					int x=sta[top--];
    					e2[vcnt].push_back(x);
    					e2[x].push_back(vcnt);
    					if(x==v) break;
    				}
    				e2[vcnt].push_back(u);
    				e2[u].push_back(vcnt);
    				while(1)
    				{
    					int eid=sta2[top2--];
    					vcc[eid]=vcnt;
    					if(eid==fa_id[v]) break;
    				}	
    			}
    		}
    		else if(v!=fa[u])
    		{
    			low[u]=min(low[u],dfn[v]);
    			if(dfn[v]<dfn[u]) sta2[++top2]=id;
    		}
    	}	
    }
    
    int fa2[maxn<<1][21],depth[maxn<<1];
    void dfs2(int u,int f=0)
    {
    	fa2[u][0]=f;
    	for(int i=1;i<=20;++i)
    		fa2[u][i]=fa2[fa2[u][i-1]][i-1];
    	for(auto v: e2[u])
    	{
    		if(v==f) continue;
    		depth[v]=depth[u]+1;
    		dfs2(v,u); 
    	}
    }
    
    int lca(int u,int v)
    {
    	if(depth[u]<depth[v]) swap(u,v);
    	int dis=depth[u]-depth[v];
    	for(int i=0;(1<<i)<=dis;++i)
    		if(dis>>i&1) u=fa2[u][i];
    	if(u==v) return u;
    	for(int i=20;i>=0;--i)
    	{
    		if(fa2[u][i]!=fa2[v][i])
    			u=fa2[u][i],v=fa2[v][i];
    	}
    	return fa2[u][0];
    }
    int getdis(int u,int v)
    {
    	return depth[u]+depth[v]-2*depth[lca(u,v)];
    }
    int main()
    {	
    	while(scanf("%d%d",&n,&m)&&(n||m))
    	{
    		for(int i=1;i<=vcnt;++i) e2[i].clear();	
    		for(int i=1;i<=n;++i)
    		{
    			e[i].clear();
    			dfn[i]=low[i]=0;
    			fa[i]=fa_id[i]=vcc[i]=0;
    		}
    		times=0;
    		top=top2=0;	
    		for(int i=1;i<=m;++i)
    		{
    			int u,v;
    			scanf("%d%d",&u,&v);
    			e[u].push_back({v,i});
    			e[v].push_back({u,i});
    		}
    		vcnt=n;
    		for(int i=1;i<=n;++i)
    			if(!dfn[i]) 
    			{
    				dfs1(i);
    				depth[i]=0;
    				dfs2(i);
    			}
    		int q,u,v;
    		scanf("%d",&q);
    		while(q--)
    		{
    			scanf("%d%d",&u,&v);
    			printf("%d\n",getdis(vcc[u],vcc[v])/2);
    		}	
    	}
    	return 0;
    }
    

    396. 矿场搭建

    链接:https://www.acwing.com/problem/content/398/
    链接:https://www.luogu.com.cn/problem/P3225

    题意:给你一个无向图,你要建立尽量少的救援点,使得图中任意一个点被删除,每个点仍然与一个救援点相连,同时问方案数。

    思路:建圆方树后对每个点双进行分类讨论:

    • 割点数 = 0:需要建2个救援点,方案数 C s i z e 2 C_{size}^2 Csize2
    • 割点数 = 1:需要建1个救援点,且不能建在割点上,方案数comb(size-1,1)
    • 割点数 > 1:不需建救援点,方案数1
    #include <bits/stdc++.h>
    #define ll long long
    using namespace std;
    const int maxn=1000+10;
    
    int n,m;
    vector<int> e[maxn],e2[maxn<<1];
    
    int dfn[maxn],low[maxn],times=0;
    int sta[maxn],top=0,fa[maxn],vcnt;
    int in[maxn];
    
    void dfs(int u)
    {
    	dfn[u]=low[u]=++times;
    	sta[++top]=u;
    	for(auto v: e[u])
    	{
    		if(!dfn[v])
    		{
    			fa[v]=u;
    			dfs(v);
    			low[u]=min(low[u],low[v]);
    			if(dfn[u]<=low[v])
    			{
    				vcnt++;
    				while(1)
    				{
    					int x=sta[top--];
    					e2[vcnt].push_back(x);
    					e2[x].push_back(vcnt);
    					if(x==v) break;
    				}
    				e2[vcnt].push_back(u);
    				e2[u].push_back(vcnt);
    			}	
    		}
    		else if(v!=fa[u]) low[u]=min(low[u],dfn[v]);
    	}
    }
    
    
    int main()
    {
    	int Case=0;
    	while(scanf("%d",&m)&&m)
    	{
    		for(int i=1;i<=vcnt;++i) e2[i].clear();
    		for(int i=1;i<=n;++i)
    			dfn[i]=low[i]=fa[i]=in[i]=0,e[i].clear();
    		top=times=0;
    		n=1;
    		for(int i=1;i<=m;++i)
    		{
    			int u,v;
    			scanf("%d%d",&u,&v);
    			n=max({n,u,v});
    			e[u].push_back(v);
    			e[v].push_back(u);
    			in[u]++,in[v]++;
    		}
    		vcnt=n;
    		for(int i=1;i<=n;++i)
    			if(!dfn[i]) dfs(i);
    		
    		ll ans1=0,ans2=1;
    		for(int i=n+1;i<=vcnt;++i)
    		{
    			int cnt=0;
    			for(auto v: e2[i])
    				if(v<=n&&e2[v].size()>=2) cnt++; 
    			int sz=e2[i].size();
    			if(cnt==0) ans1+=2,ans2*=sz*(sz-1)/2;
    			else if(cnt==1) ans1++,ans2*=sz-1;
    		}
    		for(int i=1;i<=n;++i) if(in[i]==0) ans1++;
    		printf("Case %d: %lld %lld\n",++Case,ans1,ans2);	
    	}
    	return 0;
    }
    

    363. B城

    题意:无向图,每次删除一个节点和其他节点的边(不删除这个点),问会有多少个 有序点对(x,y) 之间无法连通。

    思路:Tarjan求圆方树

    • 如果 u 不是一个割点,那么答案就是: 2 ( n − 1 ) 2(n-1) 2(n1)
    • 如果 u 是一个割点,那么答案就是: ∑ v s i z e [ v ] × ( n − s i z e [ v ] ) + ( − s i z e [ u ] ) × s i z e [ u ] + n − 1 \sum_{v} size[v]\times (n-size[v]) +(-size[u])\times size[u] + n-1 vsize[v]×(nsize[v])+(size[u])×size[u]+n1
    #include <bits/stdc++.h>
    #define ll long long
    using namespace std;
    const int maxn=1e5+10;
    
    int n,m;
    vector<int> e[maxn];
    ll ans[maxn],num[maxn];
    int dfn[maxn],low[maxn],times=0;
    int fa[maxn],iscp[maxn];
    int rt=1;
    
    void dfs(int u)
    {
    	dfn[u]=low[u]=++times;
    	num[u]++;
    	int sum=0,cnt=0;
    	for(auto v: e[u])
    	{
    		if(!dfn[v])
    		{
    			fa[v]=u;
    			dfs(v);
    			low[u]=min(low[u],low[v]);
    			num[u]+=num[v];
    			if(dfn[u]<=low[v])
    			{
    				cnt++;
    				ans[u]+=1ll*num[v]*(n-num[v]);
    				sum+=num[v];
    				if(u!=rt||cnt>1) iscp[u]=1; 
    			}
    		}
    		else if(v!=fa[u]) low[u]=min(low[u],dfn[v]);
    	}
    	if(iscp[u]) ans[u]+=(1ll*n-sum-1)*(sum+1)+n-1;
    	else ans[u]=2ll*(n-1);
    }
    
    int main()
    {
    	scanf("%d%d",&n,&m);
    	for(int i=1;i<=m;++i)
    	{
    		int u,v;
    		scanf("%d%d",&u,&v);
    		e[u].push_back(v);
    		e[v].push_back(u); 
    	}
    	dfs(1);
    	for(int i=1;i<=n;++i)
    		printf("%lld\n",ans[i]);
    	return 0;
    }
    
    
    展开全文
    cheng__yu_ 2020-09-03 16:57:41
  • 这东西学了又忘我是真的...那么这个点就是割点 当然也要考虑这个点是根的情况 判定条件为子树大于2 板子题 #include&amp;lt;bits/stdc++.h&amp;gt; using namespace std; int read() { int _ = 0, ___...

    这东西学了又忘我是真的没救了.. 明明省选前才学的啊

    这种东西都很套路的拿到搜索树中去看

    如果一个点子树内没有边能到达这个点及其以上的节点

    那么这个点就是割点

    当然也要考虑这个点是根的情况 判定条件为子树大于2

    板子题

    #include<bits/stdc++.h>
    
    using namespace std;
    
    int read() {
        int _ = 0, ___ = 1; char __ = getchar();
        for(; !isdigit(__); __ = getchar()) if(__ == '-') ___ = -1;
        for(; isdigit(__); __ = getchar()) _ = (_ << 3) + (_ << 1) + (__ ^ 48);
        return _ * ___;
    }
    
    const int N = 1e6 + 10;
    
    int to[N << 1], head[N], nxt[N], e;
    int n, m, dfn[N], low[N];;
    int vis[N], cnt, tot;
    
    void add(int x, int y, bool k = 1) {
        to[++ e] = y; nxt[e] = head[x]; head[x] = e;
        if(k) add(y, x, 0);
    }
    
    void dfs(int x, int root, int fa) {
        int sz = 0;
        dfn[x] = low[x] = ++ cnt;
        for(int i = head[x]; i; i = nxt[i]) {
            ++ sz;
            if(!dfn[to[i]]) {
                dfs(to[i], 0, x);
                low[x] = min(low[x], low[to[i]]);
                if(root && sz >= 2 && !vis[x]) 
                    vis[x] = ++ tot;
                if(!root && low[to[i]] >= dfn[x] && !vis[x]) 
                    vis[x] = ++ tot;
            }
            else if(to[i] != fa)
                low[x] = min(low[x], dfn[to[i]]);
        }
    }
    
    int main() {
    #ifndef ONLINE_JUDGE
        freopen("3388.in", "r", stdin);
        freopen("3388.out", "w", stdout);
    #endif
        n = read(), m = read();
        for(int i = 1; i <= m; ++ i)    
            add(read(), read());
        for(int i = 1; i <= n; ++ i) 
            if(!dfn[i])
                dfs(i, 1, 0);
        printf("%d\n", tot);
        for(int i = 1; i <= n; ++ i)
            if(vis[i]) 
                printf("%d ", i);
        return 0;
    }
    
    展开全文
    lunch__ 2018-08-17 16:19:24
  • 文章目录无向图割点及判定对搜索起点的处理对重边的处理参考实现 Tarjan算法的核心思想已经在《Tarjan求无向图割边》中介绍了,不清楚的读者可以先行阅读那部分内容,这里直接从介绍割点开始。 无向图割点及判定...

    Tarjan算法的核心思想已经在《Tarjan求无向图割边》中介绍了,不清楚的读者可以先行阅读那部分内容,这里直接从介绍割点开始。

    无向图的割点及判定

    对于无向连通图 G ( V , E ) G(V,E) G(V,E),若删去点 v ∈ V v\in V vV及其邻边 ∀ u ∈ { V − v } , ( v , u ) ∈ E \forall u\in \{V-v\}, (v,u)\in E u{Vv},(v,u)E后, G G G被分为两个或更多互不连通的子图,则称 v v v割点割顶

    根据上面 d f n dfn dfn l o w low low,很容易能想出割边的方法——无向边 ( u , v ) (u,v) (u,v)是割边,当且仅当搜索树上存在 u u u的一个子节点 v v v,满足:

    d f n [ u ] ≤ l o w [ v ] dfn[u]\leq low[v] dfn[u]low[v]

    如果不明白上式,可以参考之前文章中抽象的三种图形。当 d f n [ u ] = l o w [ v ] dfn[u]=low[v] dfn[u]=low[v]时,两条链合起来状似闭环,此时无割边,但两条链 d f n dfn dfn最小的咬合点显然是割点。

    特别的,对于我们搜索的起点,上述判定方法还需限定条件,先来看一个反例:

    1/1
    2/1
    3/1
    4/1

    上图中,有唯一满足 d f n [ u ] ≤ l o w [ v ] dfn[u]\leq low[v] dfn[u]low[v] ( 1 , 2 ) (1,2) (1,2),但去掉 1 1 1后,剩余图为:

    2
    3
    4

    并没有被分为两个或以上的互不连通子图,所以这里搜索起点 1 1 1尽管满足上面的判别式,但并不是割点。

    是不是所有的搜索起点都不是割点呢?提出这个问题固然在思考,但细想却很好笑——任意点都能作为搜索起点,如果这句话成立,则任意点都不是割点。

    对搜索起点的处理

    如果搜索起点有两个以上的子树,则意味着在搜索树上,根结点出度为二或以上。根据树的性质,如果我们删去根节点及其邻边,则原树将裂解成子树个数个互不连通的树。若不明白,任意找几棵树观察便知。

    要在代码中实现上述判断,可记录从根节点出发的邻点调用的DFS次数即可,伪代码如下:

    int children = 0;
    for (int v: G[u]) {
        if (!vis[v]) {
            children++;
            dfs(v);
        }
    }
    if (children >= 2)  u是割点
    

    对重边的处理

    对割点问题而言,删去割点将会将所有相邻的重边删去,所以割点问题并不受重边影响。

    参考实现

    //
    // Created by Visors on 2020/10/29.
    //
    // 题目名:P3388 【模板】割点(割顶)
    // 题目来源:luogu
    // 题目链接:https://www.luogu.com.cn/problem/P3388
    // 算法:Tarjan
    // 用途:无向图割点
    // 时间复杂度:O(n+m)
    //
    
    #include <bits/stdc++.h>
    
    using namespace std;
    
    struct Tarjan {
        struct Edge {
            int to, next;
    
            Edge() = default;
    
            Edge(int to, int next) : to(to), next(next) {}
        };
    
        int vertexNum{}, edgeNum{};
        int cnt{};              // 当前时间戳
        int root{};             // 保存当前搜索树根
        vector<Edge> edges;
        vector<int> heads;
        vector<int> dfn;        // 时间戳
        vector<int> low;        // 最早追溯时间
        set<int> cuts;          // 割点编号集
    
        void init(int n, int m) {
            cnt = 0;
            vertexNum = n;
            edgeNum = m;
            heads.resize(vertexNum);
            fill(heads.begin(), heads.end(), -1);
            dfn.resize(vertexNum);
            low.resize(vertexNum);
            cuts.clear();
        }
    
        void addEdge(int u, int v) {
            edges.emplace_back(v, heads[u]);
            heads[u] = edges.size() - 1;
        }
    
        void dfs(int u) {
            dfn[u] = low[u] = ++cnt;
            int tot = 0;
            for (int i = heads[u]; ~i; i = edges[i].next) {
                int &v = edges[i].to;
                if (!dfn[v]) {
                    dfs(v);
                    low[u] = min(low[u], low[v]);
                    if (low[v] >= dfn[u]) {
                        tot++;
                        if (u != root || tot > 1) cuts.insert(u);   // 对树根特判
                    }
                } else low[u] = min(low[u], dfn[v]);
            }
        }
    
        void run() {
            for (int i = 0; i < vertexNum; i++)
                if (!dfn[i]) {
                    root = i;
                    dfs(i);
                }
        }
    } tarjan;
    
    int main() {
        ios_base::sync_with_stdio(false);
        cin.tie(nullptr), cout.tie(nullptr);
        int n, m;
        cin >> n >> m;
        tarjan.init(n, m);
        for (int i = 1, u, v; i <= m; i++) {
            cin >> u >> v;
            if (u == v) continue;
            u--, v--;
            tarjan.addEdge(u, v);
            tarjan.addEdge(v, u);
        }
        tarjan.run();
        cout << tarjan.cuts.size() << endl;
        bool first = true;
        for (int it:tarjan.cuts)
            if (first) {
                cout << it + 1;
                first = false;
            } else cout << ' ' << it + 1;
        cout << endl;
        return 0;
    }
    
    展开全文
    Visors 2020-10-31 14:18:19
  • 无向图割点:去掉这个点连通分量增加。 求法:当一个点为树根时,如果他的儿子数量大于一则这个点为割点,(一棵树的根节点有数量大于一的儿子那么去掉树根,这棵树不连通) 当这个点u的dfn[u]  很明显可以看出...

    无向图中割点:去掉这个点连通分量增加。

    求法:当一个点为树根时,如果他的儿子数量大于一则这个点为割点,(一棵树的根节点有数量大于一的儿子那么去掉树根,这棵树不连通)

    当这个点u的dfn[u]<=low[v]  (v是他能到的点)这个点为割点,因为当满足dfn[u]<=low[v]时v无法达u之前的点,那么去掉u这个点后连通分量必然增加如图

            很明显可以看出图二去掉u点连通分量没有增加,为图一去掉u点连通分量增加

    无向图的桥:当去掉某条边图的连通分量增加则称为此边为桥。

    求法:当碰到一个点u时dfn[u]<low[v]  (v是能通过u到达的点) 那么u到v这条边是一个桥,可以参考上面那两张图。

    展开全文
    qq_37632935 2017-09-14 17:22:54
  • KIKO_caoyue 2019-10-08 14:00:19
  • baniu8623 2019-09-25 08:25:36
  • tengfei461807914 2018-08-25 16:04:40
  • qq_45577081 2020-11-21 11:35:44
  • qq_18455665 2016-03-24 19:59:33
  • hahahaki 2020-06-16 23:55:01
  • riba2534 2018-01-16 16:28:40
  • engineoid 2020-02-06 15:16:32
  • Dan__ge 2016-05-03 17:41:50
  • Jeremy1149 2017-01-07 00:40:39
  • weixin_35489715 2021-05-25 05:34:48
  • zhongkeli 2013-04-26 15:10:09
  • zlzqq 2021-05-14 17:08:44
  • weixin_34216107 2019-01-08 01:53:23
  • w4149 2017-10-29 18:27:03
  • qq_43580151 2019-08-14 17:58:28
  • GodJing007 2019-07-26 11:36:16
  • diezai5015 2019-09-28 12:33:42
  • chaiwenjun000 2016-05-12 21:45:35
  • qq_33951440 2017-10-02 16:46:02

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 5,882
精华内容 2,352
关键字:

无向图的割点