PL6COL - 6-Kolorowanie Grafów Planarnych
Odwzorowanie c przyporządkowujące wierzchołkom grafu G liczby 1,...,k nazywać będziemy k-pokolorowaniem (wierzchołkowym) grafu G, jeżeli dla każdej pary wierzchołków sąsiednich (połączonych krawędzią) u,v mamy, że c(u) jest różne od c(v). Twoim zadaniem jest znaleźć dowolne 6-pokolorowanie podanego grafu planarnego.
Wejście
Pierwsza linia zawiera liczbę całkowitą 1<=t<=100 oznaczająca liczbę zestawów testowych. Następnie podanych jest t grafów planarnych. Każdy z grafów opisany jest w dwóch liniach. Pierwsza linia zawiera napis:
Graph with n nodes and m edges: [graf z n wierzchołkami oraz m krawędziami]
W drugiej linii wypisane są krawędzie grafu oddzielone przecinkami. Każda krawędź podana jest jako para wierzchołków: {u,v}. Wierzchołki grafu numerujemy kolejnymi liczbami: 0...,n-1.
Tekst w nawiasach [ ] nie występuje w plikach wejściowych ani wyjściowych.
Wyjście
Dla każdego przypadku testowego podaj 6-kolorowanie odpowiedniego grafu planarnego. Pokolorowanie grafu o n wierzchołkach powinno być podane w kolejnych n liniach, z których każda zawiera dwie liczby całkowite v c(v), oznaczające numer wierzchołka oraz wartość koloru przydzielonego temu wierzchołkowi.
Przykład
Wejście:
2
Graph with 3 nodes and 3 edges: [graf z 3 wierzchołkami i 3 krawędziami]
{0,1},{1,2},{2,0}
Graph with 9 nodes and 14 edges: [graf z 9 wierzchołkami i 14 krawędziami]
{0,1},{0,2},{0,5},{0,8},{1,2},{2,3},{2,4},{3,4},{4,5},{4,8},{5,6},{5,7},{5,8},{6,7}
Wyjście:
0 1
1 2
2 3
0 1
1 2
2 3
3 4
4 5
5 3
6 1
7 4
8 2
Wskazówki
Algorytm SL (Smallest Last) rozwiązuje sformułowany problem.
A function c mapping the set of vertices of a graph G into integers 1,...,k is called a k-coloring of G if for every pair of adjacent vertices u,v we have that c(u) is not equal to c(v). Find 6-coloring of a given planar graph.
Input
The first line contains an integer 1<=t<=100 denoting the number of test cases. Then, t planar graphs are given. Each graph is described by two lines. First line contains a string of the form:
Graph with n nodes and m edges:
The second line gives the edges of the graph separated with commas. Each edge is given as a pair of vertices: {u,v}. Vertices of the graph are denoted with integers 0...,n-1.
Output
For each test case print a 6-coloring of the corresponding planar graph. The coloring of a graph with n vertices shoud be given in n lines, where each line contains two integers
v c(v)
the number of a vertex and the color assigned to this vertex.
Example
Input:
2
Graph with 3 nodes and 3 edges:
{0,1},{1,2},{2,0}
Graph with 9 nodes and 14 edges:
{0,1},{0,2},{0,5},{0,8},{1,2},{2,3},{2,4},{3,4},{4,5},{4,8},{5,6},{5,7},{5,8},{6,7}
Output:
0 1
1 2
2 3
0 1
1 2
2 3
3 4
4 5
5 3
6 1
7 4
8 2
Hints
The SL algorithm (Smallest Last) solves the problem
Added by: | Darek Dereniowski |
Date: | 2005-03-30 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ERL GOSU JS-RHINO NODEJS PERL6 |
Resource: | ? |