自动搬运

查看原文

来自洛谷，原作者为

	DaiRuiChen007 白鸟白鸟 不要回头望 你要替我飞去那地方 一去那地方 那是你我共同故乡

搬运于2025-08-24 22:18:06，当前版本为作者最后更新于2024-01-13 12:18:54，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

P6165 题解

题目大意

给定 $n$ 个点，$q$ 次操作，每次连一条边，或求图中有多少个点删去后能使得图里只有链。

数据范围：$n,q\le 10^6$。

考虑第一个 $3$ 度点出现之前的状态，图里一定是环和链，如果没有环答案就是 $n$，一个环时答案是环长，否则是 $0$。

当图中出现了一个 $3$ 度点 $u$，那么删去的点一定是 $u$ 或 $u$ 的邻域，对每个点维护删除该点后的图，判断是否有环和 $3$ 度点即可知道每个点是否合法。

时间复杂度 $\mathcal O(n+q)$。

代码呈现

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e6+5;
int n,m;
struct Graph {
	int ans,del,siz[MAXN],dsu[MAXN],deg[MAXN];
	bool mrk;
	void build(int x) {
		ans=(~x)?1:n,del=x,mrk=0;
		for(int i=1;i<=n;++i) siz[i]=1,dsu[i]=i,deg[i]=0;
	}
	int find(int x) { return x^dsu[x]?dsu[x]=find(dsu[x]):x; }
	void link(int u,int v) {
		if(u==del||v==del||!ans) return ;
		if(++deg[u]>=3||++deg[v]>=3) return ans=0,void();
		u=find(u),v=find(v);
		if(u==v) {
			if(~del) ans=0;
			else {
				if(!mrk&&ans==n) ans=siz[u],mrk=1;
				else ans=0;
			}
			return ;
		}
		if(siz[u]>siz[v]) swap(u,v);
		dsu[u]=v,siz[v]+=siz[u];
	}
}	o[5];
vector <int> G[MAXN];
signed main() {
	ios::sync_with_stdio(false);
	bool flg=0;
	cin>>n>>m;
	o[0].build(-1);
	for(int x,y;m--;) {
		cin>>x;
		if(~x) {
			cin>>y,++x,++y;
			if(!flg) {
				o[0].link(x,y);
				G[x].push_back(y);
				G[y].push_back(x);
				if(G[x].size()==3) {
					o[1].build(x);
					for(int i:{0,1,2}) o[i+2].build(G[x][i]);
					for(int u=1;u<=n;++u) for(int v:G[u]) if(v>u) {
						for(int t:{1,2,3,4}) o[t].link(u,v);
					}
					flg=true;
					continue;
				}
				if(G[y].size()==3) {
					o[1].build(y);
					for(int i:{0,1,2}) o[i+2].build(G[y][i]);
					for(int u=1;u<=n;++u) for(int v:G[u]) if(v>u) {
						for(int t:{1,2,3,4}) o[t].link(u,v);
					}
					flg=true;
					continue;
				}
			} else for(int i:{1,2,3,4}) o[i].link(x,y);
		} else {
			if(!flg) cout<<o[0].ans<<"\n";
			else {
				int ans=0;
				for(int i:{1,2,3,4}) ans+=o[i].ans;
				cout<<ans<<"\n";
			}
		}
	}
	return 0;
}