Graph decomposition
Time limit2sMemory limit1024 MB
Given n and a partition of 2n-1 into parts a_i, output edge sets of K_{2n} so that each set is an a_i-factor and every edge appears in exactly one set.
- Level
Medium7 of 10
- Topics
- Graph, Combinatorics, Math
- Solved
- No attempts yet
Problem
Consider an undirected graph . An -factor of is a subgraph that contains all vertices of and some subset of the edges of , such that every vertex has degree . Such a graph is called -regular.
Let be a -regular graph, and let be a partition of into parts: . A -decomposition of is a set of graphs such that each is an -factor of , and every edge of belongs to exactly one of the graphs .
For the complete graph with an even number of vertices and a partition of into parts, construct a -decomposition of .
Input
The first line contains an integer (). The second line contains an integer , followed by the numbers (, ).
Output
Print descriptions of graphs. The description of must contain edges. Separate the graph descriptions with blank lines.