Practice Projects

Redundant Connection

Problem Statement

  • Is problem mein, tree ek undirected graph hai jo connected hota hai aur jismein koi cycles nahi hoti.

    Aapko ek graph diya gaya hai jo initially n nodes se shuru hota hai and ek additional edge add ki hai. Yeh graph ab ek aisa tree hai jismein ek extra edge added hai jise aapko identify karna hai aur remove karna hai taki resulting graph ek valid tree ban jaye.

    Input:

    • Edges array: Ek array edges diya gaya hai jiska length n hai aur har element edges[i] = [ai, bi] represent karta hai nodes ai aur bi ke beech edge ko.

    Objective:

    • Aapko ek edge return karna hai jo remove karne par graph phir se ek valid tree ban jaye jismein n nodes hon.

    • Agar multiple possible answers hain, return the edge that occurs last in the input.

    Examples:

    Example 1:

    Input: edges = [[1,2],[1,3],[2,3]] Output: [2,3]

    Explanation: Yeh graph initially connected tree hai with edges [1,2] aur [1,3]. Adding edge [2,3] se ek cycle create ho jati hai. Remove karte hain edge [2,3] taki graph phir se valid tree ban jaye.

    Example 2:

    Input: edges = [[1,2],[2,3],[3,4],[1,4],[1,5]] Output: [1,4]

    Explanation: Yeh graph initially ek tree hai. Adding edge [1,4] se ek cycle create ho jati hai. Remove karte hain edge [1,4] taki graph phir se valid tree ban jaye.

    Constraints:

    • n == edges.length

    • 3 <= n <= 1000

    • edges[i].length == 2

    • 1 <= ai < bi <= edges.length

    • ai != bi

    • There are no repeated edges.

    • The given graph is connected.

Practice Projects

Redundant Connection

Is problem mein, aapko ek graph diya gaya hai jo initially connected tree tha, aur jismein koi cycles nahi thi. Aapko ek "redundant connection" yaani aisi edge find karni hai jo add hone par pehli baar cycle create kar deti hai. Matlab, humein aisi edge identify karni hai jo graph mein ek cycle complete kar deti hai.

Intuition

Initialize with Tree: Graph ko initially ek tree me represent kiya hai. Tree connectedhota hai and usme koi cycles nahi hoti.

Add Edge to Detect Cycle: Aapko ek additional edge add karne par graph me cycle detect karni hai.

Detect First Cycle-Completing Edge:

Union-Find Algorithm: Yeh ek common algorithm hai jo cycles detect karne mein madad karta hai. Is algorithm mein hum parent aur rank arrays ka use karke union operation perform karte hain.

Union Operation: Har edge ko graph mein add karte waqt, union operation use karte hain to check if they belong to same component.

Cycle Detection: Jab humein koi aisi edge milti hai jo union operation ke baad bhi same component mein hai, woh humari redundant edge hoti hai jo cycle complete karti hai.

Approach

Time Complexity (Samay Jatilta):

  • Edge-by-Edge Checking: Har edge ke liye, humein check karna hota hai ki do nodes ke beech koi path hai ya nahi, using iterative traversal.

  • Worst-Case Traversal: Sabse badi jatilta wala case (worst case) mein yeh traversal sabhi nodes ko visit kar sakta hai, jo O(V) (V = number of nodes) hoga.

  • Repeat for Each Edge: Yeh traversal har edge ke liye repeat hota hai, jo O(E) (E = number of edges) mein hota hai.

  • Overall Time Complexity: Isliye, overall time complexity O(E + V) hoti hai, jahan E edges aur V nodes hai.

Space Complexity (Sthaan Jatilta):

  • Adjacency List: Graph ko store karne ke liye adjacency list use hoti hai jo O(V + E) space leti hai.

  • Stack & Visited Set: Traversal ke waqt, stack aur visited set ko maintain karna hota hai jo O(V) space leta hai, kyunki yeh sab nodes ko track karta hai.

  • Total Space Complexity: Isliye, total space complexity O(V + E) hoti hai.

Solution

				
					class Solution {
    findRedundantConnection(edges) {
        const graph = new Map(); // Graph ko represent karta hai as a map

        const isConnected = (u, v) => { // Check karte hain ki do nodes connected hain ya nahi
            const visited = new Set(); // Visited nodes ko track karta hai
            const stack = []; // DFS ke liye stack use karte hain
            stack.push(u); // Start karte hain node 'u' se

            while (stack.length > 0) { // Jab tak stack khali nahi hota
                const node = stack.pop(); // Stack se node nikalte hain

                if (visited.has(node)) continue; // Agar node visited hai to continue karte hain
                visited.add(node); // Node ko visited set mein add karte hain

                if (node === v) return true; // Agar node 'v' hai to return true

                (graph.get(node) || []).forEach(neighbor => { // Har neighbor ko stack mein push karte hain
                    stack.push(neighbor); 
                });
            }
            return false; // Agar path nahi milta to return false
        };

        for (const [u, v] of edges) { // Har edge ko process karte hain
            if (graph.has(u) && graph.has(v) && isConnected(u, v)) {
                return [u, v]; // Agar cycle detect hoti hai to yeh edge return karte hain
            }

            if (!graph.has(u)) graph.set(u, []); // Agar node 'u' graph mein nahi hai to new entry add karte hain
            if (!graph.has(v)) graph.set(v, []); // Agar node 'v' graph mein nahi hai to new entry add karte hain

            graph.get(u).push(v); // Edge ko graph mein add karte hain
            graph.get(v).push(u); // Reverse edge ko bhi add karte hain (undirected graph)
        }

        return []; // Agar koi redundant edge nahi milti to empty array return karte hain
    }
}

Graph Representation:

  • Graph initialize: graph ek Map object ke रूप में define kiya gaya hai. Yeh graph ko represent karta hai jahan har node ke saath uske neighbors (connected nodes) stored hain.

    javascript
    const graph = new Map();

Connectivity Check Function (isConnected):

  • isConnected function: Yeh function check karta hai ki do nodes u aur v connected hain ya nahi. Yeh DFS algorithm use karta hai using a stack.

    javascript
    const isConnected = (u, v) => {
    const visited = new Set(); // Visited nodes ko track karte hain
    const stack = []; // DFS ke liye stack use karte hain
    stack.push(u); // Start karte hain node 'u' se

  • DFS Traversal: Jab tak stack khali nahi hota, har node ko visit karte hain, aur agar visited set mein node already hai, usko skip kar dete hain. Agar current node v hai, to true return karte hain, yeh indicate karta hai ki nodes connected hain.

    javascript
    while (stack.length > 0) {
    const node = stack.pop();
    if (visited.has(node)) continue;
    visited.add(node);
    if (node === v) return true;

  • Neighbors Check: Har node ke neighbors ko stack mein push karte hain. Agar koi valid path nahi milta, to false return karte hain.

    javascript
    (graph.get(node) || []).forEach(neighbor => {
    stack.push(neighbor);
});
return false;
};
Main Function (findRedundantConnection):

  • Edge Processing: for loop use karke har edge ko process karte hain. Agar dono nodes graph mein exist karte hain aur isConnected function true return karta hai, to yeh edge redundant hai jo cycle complete karte hain.

    javascript
    for (const [u, v] of edges) {
    if (graph.has(u) && graph.has(v) && isConnected(u, v)) {
        return [u, v]; // Cycle detect hone par yeh edge return karte hain
    }

  • Add Edge to Graph: Agar nodes graph mein nahi hain, to nayi edges ko add karte hain Map mein as new entries. Yeh undirected graph ke liye hota hai isliye har connection ke liye reverse connection bhi add karte hain.

    javascript
    if (!graph.has(u)) graph.set(u, []);
if (!graph.has(v)) graph.set(v, []);
graph.get(u).push(v);
graph.get(v).push(u);

  • Return Result: Agar koi redundant edge detect nahi hoti, to empty array return karte hain.

    javascript
    return [];
}

Solution

				
					class Solution {
public:
    vector<int> findRedundantConnection(vector<vector<int>>& edges) {
        // Graph ko represent karne ke liye unordered_map use karte hain
        unordered_map<int, vector<int>> graph;

        // Connectivity check karne ke liye lambda function use karte hain
        auto isConnected = [&](int u, int v) {
            unordered_set<int> visited; // Visited nodes ko track karte hain
            stack<int> stack; // DFS ke liye stack use karte hain
            stack.push(u); // Start karte hain node 'u' se

            while (!stack.empty()) { // Jab tak stack khali nahi hota
                int node = stack.top(); // Stack ke top pe node ko lete hain
                stack.pop(); // Node ko stack se nikaal dete hain

                if (visited.count(node)) continue; // Agar node already visited hai to continue karte hain
                visited.insert(node); // Node ko visited set mein add karte hain

                if (node == v) return true; // Agar current node 'v' hai to return true

                for (int neighbor : graph[node]) { // Har neighbor ko stack mein push karte hain
                    stack.push(neighbor); 
                }
            }
            return false; // Agar koi path nahi milta to return false
        };

        for (const auto& edge : edges) { // Har edge ko process karte hain
            int u = edge[0], v = edge[1];

            if (graph.count(u) && graph.count(v) && isConnected(u, v)) {
                return edge; // Agar cycle detect hoti hai to yeh edge return karte hain
            }

            graph[u].push_back(v); // Node 'u' ko 'v' ke saath connect karte hain
            graph[v].push_back(u); // Node 'v' ko 'u' ke saath connect karte hain
        }

        return {}; // Agar koi redundant edge nahi milti to return empty array
    }
};

    • Graph Representation:

      • Graph initialize: Graph ko represent karne ke liye unordered_map use kiya gaya hai. Har node ke neighbors ko store kiya gaya hai, jaha node ke saath unke connected nodes stored hain.

        cpp
        unordered_map<int, vector<int>> graph;

      Connectivity Check Function (isConnected):

      • isConnected function: Yeh check karta hai ki do nodes u aur v connected hain ya nahi. Iske liye DFS (Depth-First Search) algorithm use kiya gaya hai using a stack.

        cpp
        auto isConnected = [&](int u, int v) { 
    unordered_set<int> visited; // Visited nodes ko track karte hain
    stack<int> stack; // DFS ke liye stack use karte hain
    stack.push(u); // Start karte hain node 'u' se

      • DFS Traversal: Jab tak stack khali nahi hota, har node ko stack se nikal kar visit karte hain. Agar wo node visited set mein pehle hi hai to usko skip kar dete hain. Agar current node v hai, to yeh return true karega, yeh indicate karta hai ki u aur v connected hain.

        cpp
        while (!stack.empty()) { 
    int node = stack.top(); // Stack ke top pe node ko lete hain
    stack.pop(); // Node ko stack se nikaal dete hain

    if (visited.count(node)) continue; // Agar node already visited hai to continue karte hain
    visited.insert(node); // Node ko visited set mein add karte hain

    if (node == v) return true; // Agar current node 'v' hai to return true

      • Neighbors Check: Har node ke neighbors ko stack mein push karte hain taki unhe bhi check kiya ja sake. Agar koi valid path nahi milta to false return karte hain.

        cpp
        for (int neighbor : graph[node]) { // Har node ke neighbors ko stack mein push karte hain
    stack.push(neighbor); 
}
return false;
};

      Main Function (findRedundantConnection):

      • Edge Processing: Sari edges ko process karte hain. Agar dono nodes graph mein exist karte hain aur isConnected function true return karta hai, iska matlab hai ki yeh edge redundant hai aur cycle complete kar rahi hai.

        cpp
        for (const auto& edge : edges) { // Har edge ko process karte hain
    int u = edge[0], v = edge[1];

    if (graph.count(u) && graph.count(v) && isConnected(u, v)) {
        return edge; // Agar cycle detect hoti hai to yeh edge return karte hain
    }

      • Add Edge to Graph: Agar nodes graph mein exist nahi karte to nayi edges ko unordered_map mein add karte hain. Yeh undirected graph ke liye hota hai, isliye har connection ke liye reverse connection bhi add karte hain.

        cpp
        graph[u].push_back(v); // Node 'u' ko 'v' ke saath connect karte hain
graph[v].push_back(u); // Node 'v' ko 'u' ke saath connect karte hain

      • Return Result: Agar koi redundant edge detect nahi hoti to empty array return karte hain.

        cpp
        return {}; 
}