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 ?
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 ?
