Is the graph algorithm decision made right?

Question

I came across a problem from the last Facebook Hacker Cup (so this is not my homework, I just find it very interesting), and I also thought of a curious, but rather good solution. Could you check my mind? Here is the task:

You are provided with a network with N cities and M bi-directional roads connecting these cities. The first cities are important K. You need to remove the minimum number of roads, so there are no cycles in the remaining network that contain important cities. A cycle is a sequence of at least three different cities in which each pair of neighboring cities is connected by a road and the first and last city in the sequence are also connected by a road.

Enter
The first line contains the number of test cases T.

Each case begins with a line containing the integers N, M, and K, which represent the number of cities, the number of roads, and the number of important cities, respectively. Cities are numbered from 0 to N-1, and important cities are numbered from 0 to K-1. The next M lines contain two integers a [i] and b [i], 0 ≤ i <M, which represent two different cities connected by a road.

It is guaranteed that 0 ≤ a [i], b [i] N and a [i] ≠ b [i]. There will be one road between the two cities.

Exit
For each of the test cases, numbered in the order from 1 to T, print “Case No. i:” followed by a single integer, the minimum number of roads that should be free of cycles that contain an important city.

Limitations
1 ≤ T ≤ 20
1 ≤ N ≤ 10000
1 ≤ M ≤ 50,000
1 ≤ K ≤ N

Example
In the first example, we have N = 5 cities that are connected M = 7 roads and cities 0 and 1. We can remove two roads connecting (0, 1) and (1, 2), and the remaining network will not contain cycles with important cities. Please note that in the remaining network there is a cycle that contains only non-important cities, and there are several ways to remove two roads and fulfill all conditions. You cannot delete only one road and destroy all cycles containing important cities.

Input example
one
5 7 2
0 1
12
14
0 2
2 4
2 3
3 4

Therefore, I thought about it this way: when plotting, let's have a separate array that stores information about how many neighbors each city makes (== how many roads are connected to this city). In the example case, city 0 has 2, city 1 has 3, and so on. Let me call these numbers the "city value" of a particular city.

After receiving all the input, we look through the entire array of city values, looking for cities with a value of 1. When you reach one, it means that it cannot be in a cycle, so we decrease its value “delete” (without loss of generality) the path connecting with its only neighbor and reducing neighboring value. After that, we recursively go to the neighborhood, checking the same thing, if the value is 1, repeat the scheme and go deeper recursively. If this is not the case, do not touch.

After this operation, we cleared all parts of the graph that are not cycles and cannot be part of one. We also got rid of all the removal of roads that made no sense. Therefore, we call another function, this time - we work only in important cities. Thus, we take vertex 1 - after using the function described in the previous paragraph, its value cannot be 1 (since it would already be a zero function), so it is either 0 or something> 1. In the first case we don’t have to do anything. In the latter case, we must make the value 1, which is performed by removing the values ​​of 1. As in the previous paragraph, after each deletion, we reduce the cost of both this city and its neighbor, also removing the road. We repeat this for all important cities, summing the value -1 from all important cities and our response.

Is there any reason? For all the tests, I tried to work, and I would like to believe it correctly, but somehow I feel that there might be a leak somewhere. Could you check it out? It's good? If not, then why is there anything right in this thinking process? :)

Answer 1

Here was the wrong decision.

Counterexample for your decision. Suppose one squared is the only important one. Your decision will remove one road.

Answer 2

If you can prove that the optimal number of cuts is equal to the number of different cycles * that contain an important node, solving the problem is not so difficult.

You can do DFS, track visited nodes, and whenever you reach a node that you have already visited, you get a loop. To find out if the loop contains an important node or not, keep track of the depth at which each node was visited, and remember the depth of the last important node in the current search branch. If the loop start depth is less (i.e., Earlier) than the last important node depth, the loop contains an important node.

C ++ implementation:

// does not handle multiple test cases #include <iostream> #include <vector> using namespace std; const int MAX = 10000; int n, m, k; vector<int> edges[MAX]; bool seen[MAX]; int seenDepth[MAX]; // the depth at which the DFS visited the node bool isImportant(int node) { return node < k; } int findCycles(int node, int depth, int depthOfLastImp) { if (seen[node]) { if (seenDepth[node] <= depthOfLastImp && (depth - seenDepth[node]) > 2) { // found a cycle with at least one important node return 1; } else { // found a cycle, but it not valid, so cut this branch return 0; } } else { // mark this node as visited seen[node] = true; seenDepth[node] = depth; // recursively find cycles if (isImportant(node)) depthOfLastImp = depth; int cycles = 0; for (int i = 0; i < edges[node].size(); i++) { cycles += findCycles(edges[node][i], depth + 1, depthOfLastImp); } return cycles; } } int main() { // read data cin >> n >> m >> k; for (int i = 0; i < m; i++) { int start, stop; cin >> start >> stop; edges[start].push_back(stop); edges[stop].push_back(start); } int numCycles = 0; for (int i = 0; i < m; i++) { if (!seen[i]) { // start at depth 0, and last important was never (-1) numCycles += findCycles(i, 0, -1); } } cout << numCycles << "\n"; return 0; } 

---

* By "different" I mean that the cycle is not taken into account if all its edges are already part of different cycles. In the following example, I believe that the number of cycles is 2, not 3:

  A–B | | C–D | | E–F 

Answer 3

My algorithm is based on the following observation: since we don’t need cycles only with unimportant nodes, unimportant nodes can be collapsed. We destroy two neighboring unimportant nodes, replacing them with one non-essential node by the sum of the edges from the original nodes.

When folding two unimportant nodes, we need to handle two special cases:

• Both nodes were associated with the same non-essential node U. This means that there was a cycle of non-essential nodes in the original graph; we can ignore the loop, and the new node will be connected to the same non-essential node U with a single edge.
• Both nodes were associated with the same important node I. This means that there is a loop of unimportant nodes and the only important node I in the original graph; Before collapsing nodes, we need to remove one of the edges connecting them to the important node I, and thereby delete the loop; The new node will be connected to the important node I with one edge.

Given the above definition of node, the algorithm:

• Continue to collapse neighboring unimportant nodes until there are no neighboring unimportant nodes. All deleted edges between nodes important and non-essential , as defined in example (2) above, take into account the solution.
• Find the spanning tree of the remaining graph and remove all edges that are not included in the spanning tree. All edges removed in this step are taken into account in the solution.

The algorithm runs in O (M) time. I believe that I can prove my correctness, but I would like to receive your feedback before I spend too much time on this :-)