标签：并查集，分类讨论
题目
分析
分类讨论
如果所有点的度数都<=2，那么进行简单情况的讨论
- 如果全部为链式结构，那么输出n
- 如果有一个环，那么输出环的大小
- 如果存在多个环，那么无解
如果存在任意一点的度数>2，那么进行复杂情况的讨论
为了保证链的连通性，我们要么删掉它，要么当它度数为3时，删去相邻三个点之一
在加边过程中出现第一个度数为3的点，对于可能是答案的4个点分别维护去掉它之后的图
用一个记录集合大小的并查集进行link操作和查询操作维护即可
时间复杂度O(n log n)
code
brute
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#include<set>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define ll long long
#define mem(x,num) memset(x,num,sizeof x)
#define reg(x) for(int i=last[x];i;i=e[i].next)
#define lson (x<<1)
#define rson (x<<1|1)
#define mid ((l+r)>>1)
#define pi acos(-1)
#define mp make_pair
#define pb push_back
#define pa pair<int,int>
#define fi first
#define se second
#define lowbit(x) ((x)&(-x))
using namespace std;
inline ll read(){
ll f=1,x=0;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
inline ll getgcd(ll x,ll y){return !x?y:getgcd(y%x,x);}
inline ll getlcm(ll x,ll y){return x/getgcd(x,y)*y;}
inline ll qpow(int x,int y,int p){
ll re=1;
while(y){
if(y&1)re=(re*x)%p;
y>>=1,x=(x*x)%p;
}
return re;
}
//**********head by yjjr**********
const int maxn=1e5+6;
char ch[2];
int n,m,last[maxn],vis[maxn],cnt,du[maxn];
struct edge{int to,next,w,self;}e[maxn<<2];
void insert(int u,int v){
e[++cnt]=(edge){v,last[u],1,u};last[u]=cnt;
e[++cnt]=(edge){u,last[v],1,v};last[v]=cnt;
du[u]++;du[v]++;
}
void dfs(int x,int fr){
vis[x]++;if(vis[x]>=2)return;
for(int i=last[x];i;i=e[i].next){
if(e[i].w==-1||e[i].to==fr)continue;
dfs(e[i].to,x);
}
}
inline bool check(){
mem(vis,0);
rep(i,1,n){
if(du[i]>2)return 0;
}
rep(i,1,n)if(vis[i]==0){
dfs(i,0);//cout<<i<<"E"<<endl;
//rep(j,1,n)cout<<vis[j]<<' ';cout<<"TT\n";
}
//rep(i,1,n)cout<<vis[i]<<' ';cout<<endl;
rep(i,1,n)if(vis[i]>1)return 0;
return 1;
}
void query(){
int ans=0;
rep(i,1,n){
rep(j,1,cnt)if((e[j].self==i)||(e[j].to==i)){e[j].w=-1;du[e[j].self]--;du[e[j].to]--;}
if(check())ans++;//cout<<i<<'r'<<endl;
rep(j,1,cnt)if((e[j].self==i)||(e[j].to==i)){e[j].w=1;du[e[j].self]++;du[e[j].to]++;}
}
cout<<ans<<endl;
}
int main()
{
n=read(),m=read();
rep(i,1,m){
scanf("%s",ch);
if(ch[0]=='L'){
int u=read(),v=read();
insert(u,v);
}
if(ch[0]=='Q')query();
}
return 0;
}
正解
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#include<set>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define ll long long
#define mem(x,num) memset(x,num,sizeof x)
#define reg(x) for(int i=last[x];i;i=e[i].next)
#define lson (x<<1)
#define rson (x<<1|1)
#define mid ((l+r)>>1)
#define pi acos(-1)
#define mp make_pair
#define pb push_back
#define pa pair<int,int>
#define fi first
#define se second
#define lowbit(x) ((x)&(-x))
using namespace std;
inline ll read(){
ll f=1,x=0;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
inline ll getgcd(ll x,ll y){return !x?y:getgcd(y%x,x);}
inline ll getlcm(ll x,ll y){return x/getgcd(x,y)*y;}
inline ll qpow(int x,int y,int p){
ll re=1;
while(y){
if(y&1)re=(re*x)%p;
y>>=1,x=(x*x)%p;
}
return re;
}
//**********head by yjjr**********
const int maxn=1e5+6;
int n,m,tot=0,flag=0;
char ch[2];
struct Graph{
struct sets{
int fa[maxn],setsize[maxn];
sets(){rep(i,1,maxn)fa[i]=i,setsize[i]=1;}
inline int find(const int x){return x==fa[x]?x:fa[x]=find(fa[x]);}
inline bool merge(const int x,const int y){
int r1=find(x),r2=find(y);
if(r1==r2)return 0;else fa[r1]=r2,setsize[r2]+=setsize[r1];return 1;
}
}set;
int size,cnt,node_erased,node_si,du[maxn];
Graph(){size=0;cnt=0;node_erased=-1;node_si=-1;}
void ins(const int u,const int v){
if(u!=node_erased&&v!=node_erased){
du[u]++,du[v]++;
if(!set.merge(u,v))cnt++,size=set.setsize[set.find(u)];
if(du[u]==3)node_si=u;
if(du[v]==3)node_si=v;
}
}
inline bool query(){return cnt==0&&node_si==-1;}
}G[5];
vector< int > p[maxn];
vector< pair < int,int > > e;
int main(){
n=read(),m=read();
while(m--){
scanf("%s",ch);
if(ch[0]=='Q'){
if(flag){
int ans=0;rep(i,1,4)if(G[i].query())ans++;
printf("%d\n",ans);
}else{
if(G[0].cnt==0)printf("%d\n",n);
else if(G[0].cnt==1)printf("%d\n",G[0].size);else puts("0");
}
}
if(ch[0]=='L'){
int u=read(),v=read();
if(flag)rep(i,1,4)G[i].ins(u,v);
else{
p[u].pb(v);p[v].pb(u);e.pb(mp(u,v));G[0].ins(u,v);
if(G[0].node_si!=-1){
flag=1;int t=0;
G[++t].node_erased=G[0].node_si;
for(vector<int>::iterator it=p[G[0].node_si].begin();it!=p[G[0].node_si].end();it++)G[++t].node_erased=*it;
for(vector< pair<int,int> >::iterator it=e.begin();it!=e.end();it++)
rep(i,1,4)G[i].ins((*it).first,(*it).second);
}
}
}
}
return 0;
}
