Problem link : http://acm.sgu.ru/problem.php?contest=0&problem=101
Problem summery: You're given N (N <= 100) dominoes. Each of the dominoes has two numbers on it between 0 to 6, one in left side and another in right side. You have to arrange all the dominoes in a row so that they touch through equal marked side. If not possible print "No solution". Note that, we also have to check the graph is connected.
For example, we have three dominoes [1 2], [3, 2], [3 4]
If we arrange these dominoes like this -
[1 2] - [3 2] - [3, 4], this is invalid, because right side of first domino and left side of second domino marked with different numbers. But if we flip the second domino, to change left and right side, it will become -
[1 2] - [2 3] - [3 4], now every two adjacent dominoes touches with equal marked side. So it's a valid arrangement. So to organize it like this, we are allowed to rearrange dominoes and rotate any domino.
To solve this problem, we cannot try all possible arrangements because number of arrangements is too large. As the dominoes are marked with numbers between 0 to 6, we can consider we have a graph of 7 nodes named 0 to 6. If there is a domino [a b], we will consider there is an edge between a and b. Now we have a graph of at most 7 nodes and at most 100 edges. Our problem can be described as - is it possible to start traversing from one node and visit each of the edges exactly once?
Let's use the example from the problem. We have 5 dominoes [1 2], [2 4], [2 4], [6 4], [2 1]. We can build our graph like this -
And what about the solution? See the following image, yes we can traverse all edges exactly once.
The path we traversed is 4 -> 2 -> 1 -> 2 -> 4 -> 6. So, our domino arrangement will be, [4 2] - [2 1] - [1 2] - [2 4] - [4 6], if we write the indices of the dominoes this sequence is 2, 5, 1, 3, 4. Note that we flipped one [2 4] tile to [4 2] and [6 4] tile to [4 6]. We also need to output which domino we used as it is by a '+' sign, and which domino we flipped by a '-' sign. So our answer is -
2 -
5 +
1 +
3 +
4 -
Which is also given in the sample output.
Leonhard Euler proved that, we can visit every edge exactly once in a graph if number of nodes having odd degree is not more than two. If number of odd degree in the graph is two, we have to start from one of them and end our tour in another of them. By the name of Euler, this path is called Eulerian trail or Eulerian walk. For example in our graph in the image above, node 4 and 6 have odd degree, so we started at 4 and ended at 6.
So, if the number of odd degree of the graph is more than two, we will output "No solution", otherwise we will try to print any one of the solution, by finding out the Eulerian walk. But, what will be the strategy of our Eulerian walk. We can use the strategy of Fleury's algorithm. The strategy is, start with an odd degree node if there exists any, otherwise start with any node. At each iteration we visit the edge whose deletion would not disconnect the graph.
Now, as we have n edge, so we will remove one edge at each step of our algorithm. We'll try 7 different edges and after removing that edge we'll check whether the graph is connected nor not using a dfs, in our case, which is O(n). So our algorithm is somewhat like O(n * n).
My simple C++ solution -
#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
using namespace std;
bool vis[7];
vector<int> edge_index[7][7];
int degree[7];
// can reach v from u?
bool dfs(int u, int v) {
if (u == v) {
return true;
}
vis[u] = true;
for (int i = 0; i <= 6; ++i) {
if ((edge_index[u][i].size() > 0 || edge_index[i][u].size() > 0)
&& vis[i] == false) {
if (dfs(i, v)) {
return true;
}
}
}
return false;
}
bool is_connected() {
memset(vis, 0, sizeof(vis));
for (int i = 0; i <= 6; ++i) {
if (degree[i]) {
dfs(i, -1);
break;
}
}
for (int i = 0; i <= 6; ++i) {
if (degree[i] > 0 && vis[i] == false) {
return false;
}
}
return true;
}
int main (void) {
int n; // number of dominoes i.e. number of edges
scanf("%d", &n);
memset(degree, 0, sizeof(degree));
for (int i = 0; i <= 6; ++i) {
for (int j = 0; j <= 6; ++j) {
edge_index[i][j].clear();
}
}
for (int i = 1; i <= n; ++i) {
int u, v;
scanf("%d%d", &u, &v);
edge_index[u][v].push_back(i);
degree[u]++;
degree[v]++;
}
int n_odd = 0; // number of nodes with odd degree
for (int i = 0; i <= 6; ++i) {
if (degree[i] % 2 == 1) {
n_odd++;
}
}
if (n_odd > 2 || is_connected() == false) {
// if number of odd degree node is more than 2
// eulerian path doesn't exist for this graph
printf("No solution\n");
} else {
int u = -1; // starting node
// start node with an odd degree node, if exists
for (int i = 0; i <= 6; ++i) {
if (degree[i] % 2 == 1) {
u = i;
break;
}
}
// if odd degree node not found, start with a node
// with positive degree, i.e. start with any vertex,
// which is used in the graph
if (u == -1) {
for (int i = 0; i <= 6; ++i) {
if (degree[i] > 0) {
u = i;
break;
}
}
}
// Fleury's algorithm
// n steps - at each step, remove one edge
for (int i = 0; i < n; ++i) {
int selected_ind;
bool forward_selected;
for (int j = 0; j <= 6; ++j) {
if (edge_index[u][j].size() > 0 ||
edge_index[j][u].size() > 0) {
int cur_ind;
bool forward;
if (edge_index[u][j].size() > 0) {
cur_ind = edge_index[u][j].back();
edge_index[u][j].pop_back();
forward = true;
} else {
cur_ind = edge_index[j][u].back();
edge_index[j][u].pop_back();
forward = false;
}
degree[u]--;
degree[j]--;
memset(vis, 0, sizeof(vis));
if (degree[u] == 0 || dfs(u, j) == true) {
// remove this edge
selected_ind = cur_ind;
forward_selected = forward;
u = j; // so we are in j now.
break;
} else {
// this edge cannot be removed
// back to previous state
if (forward) {
edge_index[u][j].push_back(cur_ind);
} else {
edge_index[j][u].push_back(cur_ind);
}
degree[u]++;
degree[j]++;
}
}
}
printf("%d %c\n", selected_ind, forward_selected ? '+' : '-');
}
}
return 0;
}
No comments:
Post a Comment