Codeforces 9E
Hexadecimal likes drawing. She has drawn many graphs already, both directed and not. Recently she has started to work on a still-life «interesting graph and apples». An undirected graph is called interesting, if each of its vertices belongs to one cycle only — a funny ring — and does not belong to any other cycles. A funny ring is a cycle that goes through all the vertices just once. Moreover, loops are funny rings too.
She has already drawn the apples and some of the graph edges. But now it is not clear, how to connect the rest of the vertices to get an interesting graph as a result. The answer should contain the minimal amount of added edges. And furthermore, the answer should be the lexicographically smallest one. The set of edges (x1, y1), (x2, y2), ..., (xn, yn), where xi ≤ yi, is lexicographically smaller than the set (u1, v1), (u2, v2), ..., (un, vn), where ui ≤ vi, provided that the sequence of integers x1, y1, x2, y2, ..., xn, yn is lexicographically smaller than the sequence u1, v1, u2, v2, ..., un, vn. If you do not cope, Hexadecimal will eat you. ...eat you alive.
The first line of the input data contains a pair of integers n and m (1 ≤ n ≤ 50, 0 ≤ m ≤ 2500) — the amount of vertices and edges respectively. The following lines contain pairs of numbers xi and yi (1 ≤ xi, yi ≤ n) — the vertices that are already connected by edges. The initial graph may contain multiple edges and loops.
In the first line output «YES» or «NO»: if it is possible or not to construct an interesting graph. If the answer is «YES», in the second line output k — the amount of edges that should be added to the initial graph. Finally, output k lines: pairs of vertices xj and yj, between which edges should be drawn. The result may contain multiple edges and loops. k can be equal to zero.
3 2
1 2
2 3
YES
1
1 3
题意：给出n个点，m条边，问是否能通过加一些边，使得n个点构成有且仅有n条边的单个环。如果能，输出YES以及加上的边的条数，并按字典序打印加上的边的两个端点。如果有多组解，输出字典序最小的一种方法。否则输出NO即可。
题解：并查集。不难发现，在完整的一个环中，所有节点的度都为2。因此，对先给定的边判度数，如果有点的度数大于2，则直接输出NO。
然后对于剩下的图，我们定义，如果两点间能通过边相互到达，则两点在同一个联通块里。
首先，我们先把不在同一个联通块里，且度数≤1的两个点连起来。
然后，我们再把剩下的度数≤1的两个点连起来。
紧接着，枚举n个点，如果有点的度数为0，则让其形成自环。
最后判断n个点的联通块是否与第一个点相同即可判断能否只形成一个环。
当然中间也有些小细节，比如，连边时注意将两个点用并查集并到一个联通块集合中等等，详见代码。
1 #include<bits/stdc++.h> 2 using namespace std; 3 const int N=55; 4 int n,m,x,y,aim,fa[N],deg[N]; 5 vector< pair<int,int> > ans; 6 int find(int x) 7 { 8 return fa[x]==x?x:fa[x]=find(fa[x]); 9 } 10 int main() 11 { 12 scanf("%d%d",&n,&m); 13 for (int i=1;i<=n;++i) fa[i]=i; 14 for (int i=1;i<=m;++i) 15 { 16 scanf("%d%d",&x,&y); 17 fa[find(x)]=find(y); 18 ++deg[x]; ++deg[y]; 19 if (deg[x]>2||deg[y]>2) return puts("NO"),0; 20 } 21 for (int i=2;i<=n;++i) 22 for (int j=1;j<i;++j) 23 if (deg[i]<=1&°[j]<=1&&find(i)!=find(j)) 24 { 25 ans.push_back(make_pair(j,i)); 26 fa[find(i)]=find(j); 27 ++deg[i]; ++deg[j]; 28 } 29 for (int i=2;i<=n;++i) 30 { 31 if (deg[i]==2) continue; 32 for (int j=1;j<i;++j) 33 if (deg[j]<=1) 34 { 35 ans.push_back(make_pair(j,i)); 36 fa[find(i)]=find(j); 37 ++deg[i]; ++deg[j]; 38 } 39 } 40 for (int i=1;i<=n;++i) 41 if (!deg[i]) ans.push_back(make_pair(i,i)); 42 aim=find(1); 43 for (int i=1;i<=n;++i) 44 if (find(i)!=aim) return puts("NO"),0; 45 printf("YES %d ",ans.size()); 46 sort(ans.begin(),ans.end()); 47 for (int i=0;i<ans.size();++i) 48 printf("%d %d ",ans[i].first,ans[i].second); 49 return 0; 50 }