4 or 5 days ago , i have a problem about constructing a graph satisfy the degree of each node , i post this on codeforces with a view to seeking for help from others. Contradict to my expectation , my blog got a lot of downvote that make my contribution from +1 to -16 , and codeforces block me from writing social content for 2 days. That was so sad:(.

Problem statement : there is a simple connected graph with n nodes , each node has a degree called d[i] construct a graph satisfy the request (the test show that there always has a solution), (n <= 10000)

i think there is a constructive algorithm and my solutions was trying to match the node with low to high degree, the first one i put all i with d[i] = 1 , in a stack called s[1] then i loop through 2 -> n, for(u : vertices with degree(i)) match with nodes in s[i] maximum with d[i] — 1 nodes , each nodes after match will decrease there degree and was pushed into s[i — 1] (i > 1) , after all trying to match all the stacks that are not empty together from high to low until all stacks are empty or there only s[1] still has some elements if so , i will make pairs between these i think that my solution was correct for the case this graph is a tree , however i think it's wrong for general graph , can u give me some idea ?

.

This problem statement is here I read the editorial but cannot understand how it works, then i came up with the sqrt decomposition solution. However i still want to grasp the full solution written in the editorial , i think the full solution of this problem may be useful for me in the future when i meet some kind of problems like that, (when sqrt solution is impossible). Thanks in advance.

Each of Farmer John's N cows (1≤N≤2⋅10^5) has a favorite color. The cows are conveniently labeled 1…N (as always), and each color can be represented by an integer in the range 1…N. There exist M pairs of cows (a,b) such that cow b admires cow a (1≤M≤2⋅10^5). It is possible that a=b, in which case a cow admires herself. For any color c, if cows x and y both admire a cow with favorite color c, then x and y share the same favorite color. Given this information, determine an assignment of cows to favorite colors such that the number of distinct favorite colors among all cows is maximized. As there are multiple assignments that satisfy this property, output the lexicographically smallest one (meaning that you should take the assignment that minimizes the colors assigned to cows 1…N in that order). Although i read the solution, i still cannot understand how the algorithm works? The solution:"If both cows b and c admire cow a then both b and c must have the same color. From now on, we can treat both b and c as the same cow; change all occurrences of c to b and merge the adjacency list of c into that of b. Repeat this process while at least two distinct cows admire the same cow. Once we reach a configuration in which a cow is admired by at most one cow this process terminates; we can just assign every cow a distinct color. If we always merge the smaller adjacency list of the two cows into the larger one then our solution runs in O((N+M)logN) time. We ensured that a few slow solutions did not pass but it is likely that many (not necessarily provable) heuristics passed anyways."

can anyone help me explain this technique, is this technique used frequently in famous contests such as icpc,ioi...? sorry for my poor english