2024初三集训模拟测试1

正解

• \(a_{i},b_{i}\) 属于同一个强连通分量，但并没有其具体的边的方向，故可以使用并查集维护连通性，求出此时的强连通分量 \(scc\) 数量 \(num\)。
  • 孤立的一个点也属于一个强连通分量。
• 若 \(num \ge x\) ，则将 \(scc\) 进行任意合并至只有 \(x\) 个强连通分量；否则无解。
• 求出边数的最小值 \(m'_{min}\) 和最大值 \(m'_{max}\) 。
  • 对于第 \(i\) 个强连通分量，若 \(|scc_{i}|=1\) ，则其内部没有边，否则其内部最少有 \(|scc_{i}|\) 条边，最多有 \(A_{scc_{i}}^{2}=(scc_{i}-1)scc_{i}\) 条边。
    • 最少情况是一个环。
    • 最多情况是一个完全子图。
  • 对于第 \(i\) 和第 \(j\) 个强连通分量，需保证 \(i\) 和 \(j\) 不能形成一个更大的强连通分量，故 \(i\) 和 \(j\) 之间最少有 \(0\) 条边，最多有 \(\dbinom{|scc_{i}|}{1}\dbinom{|scc_{j}|}{1}=|scc_{i}| \times |scc_{j}|\) 条边。
    • 最多情况是对于 \(scc_{i}\) 中的每个点，均向 \(scc_{j}\) 中的每个点连一条有向边或对于 \(scc_{j}\) 中的每个点，均向 \(scc_{i}\) 中的每个点连一条有向边。
• 若 \(m'_{min} \le m \le m'_{max}\) ，则有解；否则无解。
• 构造时，先将属于同一个强连通分量内的点形成一个强连通分量，此时可用边数减少了 \(m'_{min}\) ；接着构造剩下的 \(m-m'_{min}\) 条边，类比求边数的最小、最大值的构造方式即可。

点击查看代码

ll f[600000],c[600000],sum[600000],ans=0; 
vector<ll>scc[600000];
ll find(ll x)
{
	return (f[x]==x)?x:f[x]=find(f[x]);
}
void merge(ll x,ll y)
{
	x=find(x);
	y=find(y);
	if(x!=y)
	{
		f[x]=y;
	}
}
bool cmp(vector<ll>a,vector<ll>b)
{
	return a.size()>b.size();
}
int main()
{
	freopen("city.in","r",stdin);
	freopen("city.out","w",stdout);
	ll n,m,mm=0,x,q,a,b,minn=0,maxx=0,i,j,k,h;
	cin>>n>>m>>x>>q;
	for(i=1;i<=n;i++)
	{
		f[i]=i;
	}
	for(i=1;i<=q;i++)
	{
		cin>>a>>b;
		merge(a,b);
	}
	for(i=1;i<=n;i++)
	{
		if(f[i]==i)
		{
			ans++;
			c[i]=ans;
		}
	}
	for(i=1;i<=n;i++)
	{
		scc[c[find(i)]].push_back(i);
	}
	if(x<=ans)
	{   
		sort(scc+1,scc+1+ans,cmp);
		for(i=x+1;i<=ans;i++)
		{
			for(j=0;j<scc[i].size();j++)
			{
				scc[x].push_back(scc[i][j]);
			}
		}
		for(i=1;i<=x;i++)
		{
			minn+=(scc[i].size()>=2)*scc[i].size();
			maxx+=(scc[i].size()>=2)*scc[i].size()*(scc[i].size()-1);
			sum[i]=sum[i-1]+scc[i].size();
		}
		for(i=1;i<=x;i++)
		{
			maxx+=scc[i].size()*(sum[x]-sum[i]);
		}
		if(minn<=m&&m<=maxx)
		{
			for(i=1;i<=x;i++)
			{
				if(scc[i].size()>=2)
				{
					for(j=0;j+1<scc[i].size();j++)
					{
						cout<<scc[i][j]<<" "<<scc[i][j+1]<<endl;
						mm++;
					}
					cout<<scc[i][scc[i].size()-1]<<" "<<scc[i][0]<<endl;
					mm++;
				}
			}
			if(mm<m)
			{
				for(i=1;i<=x;i++)
				{
					for(j=0;j<scc[i].size();j++)
					{
						for(h=0;h<scc[i].size();h++)
						{
							if(h!=j&&h!=j+1&&(!(j==scc[i].size()-1&&h==0)))
							{
								cout<<scc[i][j]<<" "<<scc[i][h]<<endl;
								mm++;
								if(mm==m)
								{
									break;
								}
							}
						}
						if(mm==m)
						{
							break;
						}
						for(k=i+1;k<=x;k++)
						{
							for(h=0;h<scc[k].size();h++)
							{
								cout<<scc[i][j]<<" "<<scc[k][h]<<endl;
								mm++;
								if(mm==m)
								{
									break;
								}
							}
							if(mm==m)
							{
								break;
							}
						}
						if(mm==m)
						{
							break;
						}
					}
					if(mm==m)
					{
						break;
					}
				}
			}
		}
		else
		{
			cout<<"-1"<<endl;
		}
	}   
	else
	{
		cout<<"-1"<<endl;
	}
	fclose(stdin);
	fclose(stdout);
	return 0;
}