Exactly O(n) time & memory solution (not union-find)


  • 0
    S

    Here is my solution for the problem, which is better than the proposed one in terms of time complexity. I will add the explanation at the end.

    class Solution {
    public:
        using TGraph = vector<unordered_set<int>>;
        using TIdxs = unordered_map<int, unordered_map<int, int>>;
        queue<int> getTailVertices(const TGraph& graph) {
            queue<int> result;
            for (int i = 0; i < graph.size(); ++i) {
                if (graph[i].size() == 1) {
                    result.push(i);
                }
            }
            return result;
        }
        
        void removeTails(queue<int>& toVisit, TGraph& graph) {
            while (toVisit.size()) {
                auto vertex = toVisit.front();
                toVisit.pop();
                auto neighbour = *graph[vertex].begin();
                graph[vertex].clear();
                graph[neighbour].erase(vertex);
                if (graph[neighbour].size() == 1) {
                    toVisit.push(neighbour);
                }
            }
        }
        
        vector<int> enumerateCycle(const TGraph& graph) {
            int start = -1;
            for (int i = 0; i < graph.size(); ++i) {
                if (graph[i].size()) {
                    start = i;
                    break;
                }
            }
            
            int current = start;
            vector<bool> visited(graph.size(), false);
            vector<int> result;
            while (!visited[current]) {
                visited[current] = true;
                result.push_back(current);
                for (auto neighbour : graph[current]) {
                    if (!visited[neighbour]) {
                        current = neighbour;
                    }
                }
            }
            result.push_back(start);
            return result;
        }
        
        vector<int> findRedundantConnection(vector<vector<int>>& edges) {
            TGraph graph(edges.size());
            TIdxs indices;
            for (int i = 0; i < edges.size(); ++i) {
                auto edge = edges[i];
                indices[edge[0] - 1][edge[1] - 1] = i;
                graph[edge[0] - 1].insert(edge[1] - 1);
                graph[edge[1] - 1].insert(edge[0] - 1);
            }
            auto tails = getTailVertices(graph);
            if (tails.empty()) {
                return edges.back();
            }
            
            removeTails(tails, graph);
            auto cycle = enumerateCycle(graph);
            int resultIdx = -1;
            for (int i = 0; i < cycle.size() - 1; ++i) {
                int start = min(cycle[i], cycle[i + 1]);
                int end = max(cycle[i], cycle[i + 1]);
                resultIdx = max(resultIdx, indices[start][end]);
            }
            return edges[resultIdx];
        }
    };
    

    The problem asks us to find an edge on the cycle which appears last. We can notice two things:

    1. There is precisely one cycle (due to graph being a tree with an additional edge).
    2. Edges which don't lie on the cycle lie on paths attached to the cycle where every vertex (except the one lying on the cycle and the leaf one) has degree 2.

    Based on the above thoughts we can notice that one way of getting the solution would be to remove all the edges which are not on the cycle and then just pick and edge which suits the problem criterion.

    In order to remove the edges which don't lie on the cycle we can start from leaf vertices, every leaf vertex has only one edge and it is obviously not on the cycle. If we remove all the edges attached to leaf vertices we may get more leaf vertices, so we will perform the same operation until we have no leaf vertices which will mean that we are left with only vertices with degree greater than 2 and therefore have only edges which are on the cycle.

    After that we only need to iterate on the cycle and pick the latest-appearing edge.

    To make the process simple we can put all leaves in a queue and remove edges attached to them, adding new leaves to the same queue. After that we need only enumerate the remaining vertices in order of their edges and pick the edge which appears last.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.