#9 (Div. 2 Only) E. Interesting Graph and Apples （并查集+构造图）

r囧r小猫 2022-06-17 14:08 90阅读 0赞

题目链接:

[点击打开链接][Link 1]

http://codeforces.com/contest/9/problem/E

题意：

规定一个图的所有点都在一个环内，这个图就是一个环，然后给你一些边，让你添加一些边使之成为一个环且你构造的解的字典序应该是最小的。

题解：

并查集+构造图。首先所有点应该都是度数为2的。那么存在一个度数大于2的，显然就是NO。然后我们开始暴力连接两个不是在一个连通块，且度数小于等于1的两个点。然后再暴力连接同一个连通块的两个端点。最后还要判断只有一个点的那种情况，再判断一遍是否非法。最后sort一下，按序输出就可以啦。

AC代码：

#include <bits/stdc++.h>
    using namespace std;
    int fa[55];
    int e1[2510],e2[2510];
    int degree[55];
    vector<pair<int,int>>ans;
    int find(int x)
    {
    	return fa[x]==x?x:fa[x]=find(fa[x]);
    }
    void Union(int x,int y)
    {
    	int p1=find(x);
    	int p2=find(y);
    	if(p1!=p2){
    		fa[p2]=p1;
    	}
    	
    }
    int main()
    {
    	int n,m;
    	cin>>n>>m;
    	for(int i=1;i<=m;i++){
    		cin>>e1[i]>>e2[i];
    	}
    	for(int i=1;i<=n;i++) fa[i]=i;
    	for(int i=1;i<=m;i++)
    	{
    		Union(e1[i],e2[i]);
    		degree[e1[i]]++; 
    		degree[e2[i]]++;
    		if(degree[e1[i]]>2 || degree[e2[i]]>2)
    		return 0*printf("NO");
    	}
    	
    	for(int i=1;i<=n;i++)
    	{
    		for(int j=1;j<i;j++)
    		{
    			if(degree[i]<=1 && degree[j]<=1  && find(i)!=find(j))
    			{
    				ans.push_back(make_pair(j,i));
    				Union(i,j);
    				degree[i]++;
    				degree[j]++;
    			}
    		}
    	}
    	for(int i=1;i<=n;i++)
    	{
    		if(degree[i]==2)continue;
    		for(int j=1;j<i;j++)
    		{
    			if(degree[j]==1)
    			{
    				ans.push_back(make_pair(j,i));
    				Union(i,j);
    				degree[i]++;
    				degree[j]++;
    			}
    		}
    	}
    	for(int i=1;i<=n;i++)
    	{
    		if(degree[i]==0){
    			ans.push_back(make_pair(i,i));
    		}
    	}
    	
    	int p = find(1);
    	for(int i=1;i<=n;i++)
    	{
    		if(find(i)!=p) return 0*printf("NO");
    	}
    	puts("YES");
    	sort(ans.begin(),ans.end());
    	cout<<ans.size()<<endl;
    	for(int i=0;i<ans.size();i++)
    	{
    		cout<<ans[i].first<<" "<<ans[i].second<<endl;
    	}
    	return 0;
    }

[Link 1]: http://codeforces.com/contest/9/problem/E