[Subject link]
http://acm.hdu.edu.cn/showproblem.php?pid=2454
[Paste from someone else’s blog]
Blog address: https://www.cnblogs.com/debugcool/archive/2011/04/23/HDOJ2454.html
In a word, the Havel theorem of vertex degree sequence~
Definition: Given the vertex degree sequence {dn} of an undirected graph, it is required to judge whether a simple undirected graph can be constructed.
Analysis:
The greedy method is to sort the vertices in order of degree from largest to smallest, take the point Vi with the largest degree, and connect it with the vertices Vj with the larger degree in turn , And subtract the degree of Vj at the same time. After the connection is completed, Vi is no longer considered, and the remaining points are sorted again and then connected to the one with the largest degree… In this way, a feasible solution can be constructed.
There are two places to judge that there is no solution. If the degree of Vi selected in a certain time is more than the remaining vertices, there is no solution; if the degree of Vj is reduced to a negative number in a certain time, there is no solution.
As for what the Havel theorem is, the above construction process is enough~
The simple proof of the theorem is as follows:
(<=) If d'can be simplified graphically, we only need Just connect the maximum degree point in the original picture with the d1 point with the middle degree maximum in d', and the picture must be a simple picture if it is easy to get.
(=>) If d can be simply graphed, let the obtained simple graph be G. Consider two situations:
(a) If there are edges in G, remove these edges to form a simple graph G’, so d’can be simply graphed into G’
(b) If there is a point Vi, Vj makes i=dj, there must be k such that (Vi, Vk) is in G but (Vj, Vk) is not in G. At this time, we can make GG=G-{(Vi,Vk),(V1,Vj)}+{(Vk,Vj),(V1,Vi)}. The degree sequence of GG is still d, and we are back to case (a).
[Own understanding]
I really appreciate the blog analysis provided by the older brother above, otherwise I have been autistic all afternoon.
In fact, if I just want to think about it, I just think of matching. I never thought that there could be such a theorem.
This Havel theorem is actually a basis for judgment.
1. Sort by degree from largest to smallest, and then build edges in turn.
2. The process of building an edge is based on this point, and the rest are its target points, and then everyone is reduced by one
Attention! ! ! ! Must be the top k largest.
The final step is to determine whether this degree array is all zeros.
Here is the code:
1 #include
2 #include
3 #include
4 using namespace std;
5
6 const int N = 1e3 + 10;
7 int a[N];
8
9 int main()
10 {
11 int T, n;
12 for (cin >> T; T; T-- ){
13 int tot = 0, edge = 0;
14 cin >> n;
15 //for( int i=1;i<=n;i++) cin >> a[i] ;
16
17 for( int i=1;i<=n;i++ ){
18 cin >> a[i];
19 tot += a[i];
20 }
21
22
23 // Determine in-degree and out-degree
24 if( tot & 1) {
25 printf("no ");
26 continue;
27 }
28 // Sort, from largest to smallest
29 sort (a+1, a+1+n, [](int u,int v){return u>v;} );
30
31 bool flag = true;
32 for(int i = 1; flag && i <= n; i++ ){
33 for(int j=i+1; a[i] && j<=n ;j++ ){
34 if( a[j] == < span style="color: #800080;">0) continue;
35 a[i] --;
36 a[j] --;
37 }
38 //Note that you need to take the top K after each operation.
39 sort( a+i+1, a+1+n ,[](int u,int v){return u>v;} );
40 }
41 for(int i=1;i<=n;i++){
42 //cout << a[i] << "";
43 if( a[i] != 0 ){
44 flag = false;
45 }
46 }
47 if( flag) puts("yes");
48 else puts("no");
49 }
50 return 0;
51 }
Degree Sequence of Graph G
1 #include
2 #include
3 #include
4 using namespace std;
5
6 const int N = 1e3 + 10;
7 int a[N];
8
9 int main()
10 {
11 int T, n;
12 for (cin >> T; T; T-- ){
13 int tot = 0, edge = 0;
14 cin >> n;
15 //for( int i=1;i<=n;i++) cin >> a[i] ;
16
17 for( int i=1;i<=n;i++ ){
18 cin >> a[i];
19 tot += a[i];
20 }
21
22
23 // Determine in-degree and out-degree
24 if( tot & 1) {
25 printf("no ");
26 continue;
27 }
28 // Sort, from largest to smallest
29 sort (a+1, a+1+n, [](int u,int v){return u>v;} );
30
31 bool flag = true;
32 for(int i = 1; flag && i <= n; i++ ){
33 for(int j=i+1; a[i] && j<=n ;j++ ){
34 if( a[j] == < span style="color: #800080;">0) continue;
35 a[i] --;
36 a[j] --;
37 }
38 //Note that you need to take the top K after each operation.
39 sort( a+i+1, a+1+n ,[](int u,int v){return u>v;} );
40 }
41 for(int i=1;i<=n;i++){
42 //cout << a[i] << "";
43 if( a[i] != 0 ){
44 flag = false;
45 }
46 }
47 if( flag) puts("yes");
48 else puts("no");
49 }
50 return 0;
51 }
Degree Sequence of Graph G
1 #include
2 #include
3 #include
4 using namespace std;
5
6 const int N = 1e3 + 10;
7 int a[N];
8
9 int main()
10 {
11 int T, n;
12 for (cin >> T; T; T-- ){
13 int tot = 0, edge = 0;
14 cin >> n;
15 //for( int i=1;i<=n;i++) cin >> a[i] ;
16
17 for( int i=1;i<=n;i++ ){
18 cin >> a[i];
19 tot += a[i];
20 }
21
22
23 // Determine in-degree and out-degree
24 if( tot & 1) {
25 printf("no ");
26 continue;
27 }
28 // Sort, from largest to smallest
29 sort (a+1, a+1+n, [](int u,int v){return u>v;} );
30
31 bool flag = true;
32 for(int i = 1; flag && i <= n; i++ ){
33 for(int j=i+1; a[i] && j<=n ;j++ ){
34 if( a[j] == < span style="color: #800080;">0) continue;
35 a[i] --;
36 a[j] --;
37 }
38 //Note that you need to take the top K after each operation.
39 sort( a+i+1, a+1+n ,[](int u,int v){return u>v;} );
40 }
41 for(int i=1;i<=n;i++){
42 //cout << a[i] << "";
43 if( a[i] != 0 ){
44 flag = false;
45 }
46 }
47 if( flag) puts("yes");
48 else puts("no");
49 }
50 return 0;
51 }