Graph algorithm solution done right?

Question

I stumbled upon a problem from the last Facebook Hacker Cup (so it's NOT my homework, I just find it very interesting) and I also thought of a curious, but rather good, solution. Could you please check my thought? Here is the task:

You are given a network with N cities and M bidirectional roads connecting these cities. The first K cities are important. You need to remove the minimum number of roads such that in the remaining network there are no cycles that contain important cities. A cycle is a sequence of at least three different cities such that each pair of neighbouring cities are connected by a road and the first and the last city in the sequence are also connected by a road.

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

Each case begins with a line containing integers N, M and K, which represent the number of cities, the number of roads and the number of important cities, respectively. The cities are numbered from 0 to N-1, and the important cities are numbered from 0 to K-1. The following M lines contain two integers a[i] and b[i], 0 ≤ i < M, that 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 at most one road between two cities.

Output
For each of the test cases numbered in order from 1 to T, output "Case #i: " followed by a single integer, the minimum number of roads that need to be removed such that there are no cycles that contain an important city.

Constraints
1 ≤ T ≤ 20
1 ≤ N ≤ 10000
1 ≤ M ≤ 50000
1 ≤ K ≤ N

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

Example input
1
5 7 2
0 1
1 2
1 4
0 2
2 4
2 3
3 4

So I thought of it that way: while building the graph, let's have a separate array storing information on how many neighbors does every city have (==how many roads are there connected to the given city). In the example case, city 0 has 2, city 1 has 3 and so on. Let's call this numbers a "city value" of a particular city.

After obtaining the whole input, we go through the whole array of city values looking for cities with value 1. When getting to one, it means it can't be in a cycle so we decrement its value, "delete" (without the loss of generality) the road connecting it to its only neighbor and decrement the neighbor's value. After that, we recursively go to the neighbor checking for the same thing, if the value is 1 there - repeat the scheme and recursively go deeper. If it's not - don't touch.

After that operation we've cleared all the parts of the graph which are not cycles and can't be a part of one. We also got rid of all the roads removing which didn't make sense whatsoever. So we call another function, this time - working only on the important cities. So we take the vertex 1 - after the use of the function described in the previous paragraph, its value can't be 1 (as it would have already been made zero by the function) so it's either 0 or something >1. In the first case, we don't have to do anything. In the latter, we have to make the value 1 which is done by doing value-1 removals. Similarly to the previous paragraph, after each removal, we decrement the value of both this city and its neighbor also removing the road. We repeat it for all the k important cities summing the value-1's from all of the important cities and that's our answer.

Does it make any sense? For all the tests I've tried it worked and I'd like to believe it's correct but I somehow feel there may be a leak somewhere. Could you please check it? Is it any good? If not, why and is there anything correct about this thought process? :)

Answer 1

Here was an incorrect solution.

Counterexample for your solution. Suppose, that one in square is the only one important. Your solution will delete 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 that hard.

You can do a DFS, keep track of visited nodes, and whenever you reach a node that you already visited you got a cycle. To tell whether the cycle 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 branch of the search. If the cycle's start depth is less (i.e. earlier) than the last important node's depth, the cycle 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's 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 a cycle isn't counted if all its edges are already part of different cycles. In the following example, I consider the number of cycles to be 2, not 3:

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