当前位置: 首页 > 工具软件 > gls > 使用案例 >

小G的GLS图 tarjan割点 虚点

窦涵忍
2023-12-01

链接
思路:
原来n^2暴力建边取割点肯定可以,就是太慢了,我们思考对于每个不同的质因数建立新的虚点,连向存在质因数的点,这样最多只有nlogn条边,然后想了想对于原图的性质确实是不变的。但是要注意一些细节,质因数只有1个度数的点没必要连,不然例如6 向2 3连边,2和3只有1度,那么6是割点,但其实不是,我们在建边的时候特判一下即可,还有就是质因数显然是割点,我们别把它算进去即可。复杂度 n s q r t ( 1 e 7 ) + O ( t a r j a n ) nsqrt(1e7)+O(tarjan) nsqrt(1e7)+O(tarjan),我偷懒了一下,其实可以质数筛达到 n s q r t ( 1 e 7 ) / l n ( 1 e 7 ) + O ( t a r j a n ) nsqrt(1e7)/ln(1e7)+O(tarjan) nsqrt(1e7)/ln(1e7)+O(tarjan),顺便复习一下无向图tarjan求割点,有点小麻烦,就是对于每个点维护low和dfn,如果某个点的子节点的low>=他自己说明到达不了他上面的点,那么连通分量+1,如果该节点不是当前遍历的根,那么肯定会有一个来自他父亲的连通分量,那么数量也要+1.

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

const int N=200010;
int a[N];
int dfn[N];
int low[N];
bool cut[N];
int cnt[N];
int idx;
int id[N*100];
vector<int>v[N];
int timestamp;
int root;
void dfs(int u,int fa){
	dfn[u]=low[u]=++timestamp;
	int cnt=0;
	for(auto j:v[u]){
		if(j==fa)	continue;
		if(!dfn[j]){
			dfs(j,u);
			low[u]=min(low[u],low[j]);
			if(low[j]>=dfn[u])	cnt++;
		}
		else
			low[u]=min(low[u],dfn[j]);
	}
	if(u!=root)	cnt++;
	if(cnt>=2)
		cut[u]=true;
}
vector<int>temp[N];
int main()
{
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)	cin>>a[i];
	idx=n;
	for(int i=1;i<=n;i++){
		for(int j=2;j*j<=a[i];j++)
		{
			if(a[i]%j==0)	{
				if(!id[j])	id[j]=++idx;
				temp[i].push_back(id[j]);
				cnt[id[j]]++;
				while(a[i]%j==0)	a[i]/=j;
			}
		}
		if(a[i]>1)
		{
			if(!id[a[i]])
				id[a[i]]=++idx;
			cnt[id[a[i]]]++;
			temp[i].push_back(id[a[i]]);
		}
	}
	for(int i=1;i<=n;i++)
	{
		for(auto j:temp[i])
		{
			v[i].push_back(j);
			v[j].push_back(i);
		}
	}
	for(int i=1;i<=idx;i++)
		if(!dfn[i])
			root=i,dfs(i,-1);
	int res=0;
	for(int i=1;i<=n;i++)	if(cut[i])	res++;
	cout<<res<<"\n";
	
	
	return 0;
}
 类似资料: