CF1916F Group Division 题解

upd 2024.11.20 “（否则选出这个点后 $S_2$ 就不连通了）” $S_2$ 改为 $S_1$

upd 2024.10.10 “且选出的点不是剩余点集 $S_2$ 的割点” $S_2$ 改为 $S_1$

1. 题意

   给定一个无向图 $G$，点数为 $n_1+n_2$，边数为 $m$,保证 $G$ 是一个点双连通分量且无重边。

   请将 $G$ 划分为两个无交集的点集 $S_1$，$S_2$ 满足 $|S_1|=n_1$，$|S_2|=n_2$，且 $S_1$，$S_2$ 的导出子图均连通。

   保证有解。

2. 思路

   • 因为 $ 1 \le n_1 , n_2 \le 2000 $，$ 1 \le m \le 5000 $ 所以可以考虑一个点一个点地选取和划分，每一次选取花费时间 $O\left(\log\right.m)$ 或更少。
   • 因此可以定义 $S_2$ 为空集，所有点都在 $S_1$ 中，之后，每次从 $S_1$ 取出 $1$ 个点放入 $S_2$，执行 $n_2$ 次。
   • 然后考虑怎样的点可以被选取，易得，只要保证新选出的点与 $S_2$ 连通（题目要求保证两个子图均连通）且选出的点不是剩余点集 $S_1$ 的割点（否则选出这个点后 $S_1$ 就不连通了）。
   • 于是，就可以用 Tarjan 求割点解决了。

3. 注意

   • 每次求割点之前一定要清空相关数组。
   • 注意多测要清空存图的 vector。
   • 注意取出的点要在 $S_1$ 删除。
   • 开始时先取任意一点放入 $S_2$ 并注意要在 $S_1$ 中删点。

4. 代码

   //#include<bits/stdc++.h>
   #include<iostream>
   #include<vector>
   #include<algorithm>
   #include<cstring>
   #include<set>
   using namespace std;
   const int maxn=20000;
   vector<int>G[maxn+100];
   vector<int>GG[maxn+100];
   int dfn[maxn+100]，low[maxn+100]，tot;
   int n，m;
   int cut[maxn+100];
   void del_point(int p){
   	for(auto po:G[p]){
   		for(int i=0;i<G[po].size();i++){
   			if(G[po][i]==p){
   				G[po].erase(G[po].begin()+i);
   			}
   		}
   	}
   	G[p].clear();
   }
   void Tarjan(int u，int root){
   	low[u]=dfn[u]=++tot;
   	int cnt=0;
   	for(auto v:G[u]){
   		if(!dfn[v]){
   			Tarjan(v，root);
   			low[u]=min(low[u]，low[v]);
   			if(low[v]>=dfn[u])cnt++;
   		}
   		else{
   			low[u]=min(low[u]，dfn[v]);
   		}
   	}
   	if(u==root){
   		if(cnt>1)cut[u]=1;
   	}
   	else 
   		if(cnt>0)cut[u]=1;
   }
   void find_cut(){
   	for(int i=1;i<=n;i++){
   		if(dfn[i])continue;
   		Tarjan(i，i);
   	}
   }
   bool ans[maxn+100];
   void init(bool x){
   	memset(dfn，0，sizeof(dfn));
   	memset(low，0，sizeof(low));
   	memset(cut，0，sizeof(cut));
   	tot=0;
   	if(x){
   		memset(ans，0，sizeof(ans));
   		memset(G，0，sizeof(G));
   		memset(GG，0，sizeof(GG));
   	}
   }
   int CASEmain(){
   	init(true);
   	int n1，n2;
   	cin>>n1>>n2>>m;
   	n=n1+n2;
   	for(int i=1;i<=m;i++){
   		int u，v;
   		cin>>u>>v;
   		G[u].push_back(v);
   		G[v].push_back(u);
   		GG[u].push_back(v);
   		GG[v].push_back(u);
   	}
   	cout<<1<<" ";
   	ans[1]=1;
   	del_point(1);
   	for(int i=1;i<n1;i++){
   		init(false);
   		find_cut();
   		set<int>ps;
   		for(int j=1;j<=n;j++){
   			if(ans[j]){
   				for(auto k:GG[j]){
   					ps.insert(k);
   				}
   			}
   		}
   		for(auto j:ps){
   			if(!cut[j]&&G[j].size()!=0){
   				cout<<j<<" ";
   				ans[j]=1;
   				del_point(j);
   				break;
   			}
   		}
   	}
   	cout<<endl;
   	for(int i=1;i<=n;i++){
   		if(!ans[i])
   			cout<<i<<" ";
   	}
   	cout<<endl;
   	return 0;
   }
   int main(){
   	int t;
   	cin>>t;
   	for(int i=1;i<=t;i++){
   		CASEmain();
   	}
   	return 0;
   }