Graph Coloring#3163
You are to write a program that tries to find an optimal coloring for a given graph. Colors are applied to the nodes of the graph, and only two colors are available: black and white. The coloring of the graph is called optimal if it maximizes the number of black nodes. The coloring must satisfy the rule that no two adjacent nodes can both be black.
Figure 1: An optimal graph coloring with three black nodes
The graph is specified by a set of nodes numbered from to , n \leq 100, and a set of undirected edges given as pairs of node numbers (n_1, n_2), n_1 \neq n_2. The input contains graphs. The first line contains the number . The description of each graph begins with a line containing and —the number of nodes and edges, respectively. The following lines contain the edges, each given as a pair of node numbers separated by a space.
The output should contain lines, two lines for each graph from the input. The first of the two lines should contain the maximum number of nodes that can be colored black in the graph. The second line should contain one possible optimal coloring, given as a list of the black nodes separated by spaces.
Beispiel 1