http://uva.onlinejudge.org/external/101/10178.html
You are given a planar graph. A planar graph is one that can be drawn on a plane in such a way that there are no “edge crossings,” i.e. edges intersects only at their common vertices. Your task is to print the number of faces in that graph.
For example the following graph has 6 faces:
To solve this problem the first thing that we need to do is understand about the faces and how these are created. To simplify things let's forget about the outer face (face #6) and focus in the others. It is not hard to see that the rest of the faces are enclosed regions of 3 or more points, in other words there are cycles. This implies that the problem of counting the cycles in an undirected planar graph is analogous to the number of faces in the graph, with the only exception that we should not use an edge more than one time.
To count the cycles in an undirected planar graph we are going to use the Disjoint Sets data structure.
In order to better illustrate this ideas let's take a look to an example:
Imagined that we are using the operation \(union\_set(x,y)\) for all the edges in the previous graph. Let's assume that we connect the edges in the following order \((A, B)\) - \((B, D)\) - \((D, C)\) - \((C, A)\) - \((C, E)\) - \((E, G)\) - \((G, A)\). A green edge represent a connection between two nodes were each of the nodes belong to a different connected component. In those cases we do not have a cycle. A red edge or cycle appear just in the cases were we connect two nodes that already belongs to the same component. In those cases we should increment the faces counter. Note that this idea also works where you have more than one connected component in the graph.
Once we are done with all the edges our answer is the number of cycles founded in the graph plus one. Discussing this problem with my friend cjoa2 he told me that the mathematician Leonhard Euler discover a formula to calculate the number of faces in a planar graph.
Were v and e represent the total count of vertices and edges in the graph. For example given the previous graph we have the following:
There is just a little issue in the case that we have different connected components if we applied the formula for each component we are going to end up over counting the number of outer faces. Let's see an example that illustrate this problem:
If we calculate formula for each component and add up the results we get that the total number of faces in the those planar graphs is 4, which is clearly incorrect... the correct answer should be 3:
To be able to solve this issue we are going to calculate the number of faces in each component with the following formula:
Once we sum the result of each component, we add one to our final answer, corresponding to the outer face of all the connected components.
Finally, To implement this idea we use a depth first search method that give us the total amount of vertices and edges in each connected component and used the previous explained formula.
You are given a planar graph. A planar graph is one that can be drawn on a plane in such a way that there are no “edge crossings,” i.e. edges intersects only at their common vertices. Your task is to print the number of faces in that graph.
For example the following graph has 6 faces:
To solve this problem the first thing that we need to do is understand about the faces and how these are created. To simplify things let's forget about the outer face (face #6) and focus in the others. It is not hard to see that the rest of the faces are enclosed regions of 3 or more points, in other words there are cycles. This implies that the problem of counting the cycles in an undirected planar graph is analogous to the number of faces in the graph, with the only exception that we should not use an edge more than one time.
To count the cycles in an undirected planar graph we are going to use the Disjoint Sets data structure.
In order to better illustrate this ideas let's take a look to an example:
Imagined that we are using the operation \(union\_set(x,y)\) for all the edges in the previous graph. Let's assume that we connect the edges in the following order \((A, B)\) - \((B, D)\) - \((D, C)\) - \((C, A)\) - \((C, E)\) - \((E, G)\) - \((G, A)\). A green edge represent a connection between two nodes were each of the nodes belong to a different connected component. In those cases we do not have a cycle. A red edge or cycle appear just in the cases were we connect two nodes that already belongs to the same component. In those cases we should increment the faces counter. Note that this idea also works where you have more than one connected component in the graph.
Once we are done with all the edges our answer is the number of cycles founded in the graph plus one. Discussing this problem with my friend cjoa2 he told me that the mathematician Leonhard Euler discover a formula to calculate the number of faces in a planar graph.
Were v and e represent the total count of vertices and edges in the graph. For example given the previous graph we have the following:
There is just a little issue in the case that we have different connected components if we applied the formula for each component we are going to end up over counting the number of outer faces. Let's see an example that illustrate this problem:
To be able to solve this issue we are going to calculate the number of faces in each component with the following formula:
Once we sum the result of each component, we add one to our final answer, corresponding to the outer face of all the connected components.
Finally, To implement this idea we use a depth first search method that give us the total amount of vertices and edges in each connected component and used the previous explained formula.
3 comments:
great post :D keep it up (Y)
Thanks :)
Can you give me sample input and expected output to test the code?
Post a Comment