Find if Path Exists in Graph

There is a bi-directional graph with n vertices, where each vertex is labeled from 0 to n-1 (inclusive). The edges in the graph are represented as 2D integer array edges, where each edges[i] = [ui, vi] denotes a bi-directional edge between vertex ui and vertex vi. Every vertex pair is connected by at most one edge, and no vertex has an edge to itself.

You want to determine if there is a valid path that exists from vertex start to vertex end.

Given edges and the integers n, start, and end, return true if there is a valid path from start to end, or false otherwise.

Example 1:

Input: n = 3, edges = [[0,1],[1,2],[2,0]], start = 0, end = 2
Output: true
Explanation: There are two paths from vertex 0 to vertex 2:
- 0 → 1 → 2
- 0 → 2

Example 2:

Input: n = 6, edges = [[0,1],[0,2],[3,5],[5,4],[4,3]], start = 0, end = 5
Output: false
Explanation: There is no path from vertex 0 to vertex 5.

Approach

Java

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;

public class FindPathExist {
    public static void main(String[] args) {

        int n = 3;
        int[][] edges = { { 0, 1 }, { 1, 2 }, { 2, 0 } };
        int start = 0, end = 2;

        System.out.println(validPath(n, edges, start, end));

    }

    static boolean flag = false;
    static Map<Integer, List<Integer>> adj;
    static Set<Integer> visited;

    public static boolean validPath(int n, int[][] edges, 
            int start, int end) {

        // if start is same as end then return true.
        if (start == end)
            return true;

        adj = new HashMap<>();
        visited = new HashSet<>();

        // Initializing the adjacency list and then adding
        // bidirectional edges to it

        for (int i = 0; i < n; i++) {
            adj.put(i, new ArrayList<>());
        }

        // add edges into the adjacency list
        for (int[] i : edges) {
            adj.get(i[0]).add(i[1]);
            adj.get(i[1]).add(i[0]);
        }

        // we start by marking start as visited
        visited.add(start);
        // and then we traverse using dfs
        dfs(adj.get(start), start, end);

        // at the end all we need to do is return
        return flag;
    }

    public static void dfs(List<Integer> temp, int node,
        int end) {
        if (temp == null)
            return;

        if (node == end) {
            flag = true;
            return;
        }
        // iterate through all the neighbors of current node
        for (int i : temp) {

            // if the neighbor is unvisited then just
            // visit its list too
            if (!visited.contains(i)) {
                visited.add(i);
                dfs(adj.get(i), i, end);
            }
        }

    }

}

C++

#include <bits/stdc++.h>
using namespace std;

bool flag = false;

void dfs(int node, int end, vector<bool> &vis,
      vector<vector<int>> &adj)
{

    //if current node is the end node then
    //we set flag as true as we found a path from start to end
    //and return from the function
    if (node == end)
    {
        flag = true;
        return;
    }

    //mark current node as visited so that we cannot
    //traverse the same node again and again.
    vis[node] = true;

    //iterate through all th adjacent nodes of current node
    for (int it : adj[node])
    {
        //if not visited then call for dfs
        //recursively
        if (vis[it] == false)
            dfs(it, end, vis, adj);
    }
}

bool validPath(int n, vector<vector<int>> &edges, 
       int start, int end)
{

    vector<vector<int>> adj(n);

    //create a visisted array
    vector<bool> vis(n, false);

    //create a graph from the given edges
    for (int i = 0; i < edges.size(); i++)
    {

        int u = edges[i][0];
        int v = edges[i][1];

        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    //call for dfs
    dfs(start, end, vis, adj);

    return flag;
}

int main()
{
    int n = 3;
    vector<vector<int>> edges = {{0, 1}, {1, 2}, {2, 0}};
    int start = 0, end = 2;

    if (validPath(n, edges, start, end))
        cout << "true\n";
    else
        cout << "false\n";

    return 0;
}

Find Center of Star Graph

There is an undirected star graph consisting of n nodes labeled from 1 to n. A star graph is a graph where there is one center node and exactly n - 1 edges that connect the center node with every other node.

You are given a 2D integer array edges where each edges[i] = [ui, vi] indicates that there is an edge between the nodes ui and vi. Return the center of the given star graph.

Example 1:

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

Example 2:

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

Approach

C++

#include <bits/stdc++.h>
using namespace std;

int findCenter(vector<vector<int>> &edges)
{
    set<int> st;
    int res;
    for (int i = 0; i < edges.size(); i++)
    {

        if (st.find(edges[i][0]) != st.end())
        {
            res = edges[i][0];
            break;
        }
        else if (st.find(edges[i][0]) == st.end())
            st.insert(edges[i][0]);
        if (st.find(edges[i][1]) != st.end())
        {
            res = edges[i][1];
            break;
        }
        else
            st.insert(edges[i][1]);
    }
    return res;
}

int main()
{
    vector<vector<int>> edges = {{1, 2}, {2, 3}, {4, 2}};

    cout << findCenter(edges) << "\n";

    return 0;
}

Prison Break

Alfie was a prisoner in mythland. Though Alfie was a witty and intelligent guy.He was confident of escaping prison.After few days of observation,He figured out that the prison consists of ($N\times N$) cells.i.e The shape of prison was ($N\times N$) matrix. Few of the cells of the prison contained motion detectors.So Alfie planned that while escaping the prison he will avoid those cells containing motion detectors.Yet before executing his plan,Alfie wants to know the total number of unique possible paths which he can take to escape the prison.Initially Alfie is in cell
($1,1$) while the exit of the cell ($N,N$).

note:->Alfie can move in all four direction{ if his current location is ($X,Y$), he can move to either
($X+1,Y$), ($X-1,Y$), ($X,Y+1$), ($X,Y-1$) }. If the first cell ($1,1$) and the last cell($N,N$) contain motion detectors,then Alfie can't break out of the prison.

Example:

Input:  n = 4, arr = {{0, 1, 1, 0}, {0, 0, 1, 0}, {0, 0, 0, 0}, {0, 1, 1, 0}}
Output: 2

Approach

C++

#include <bits/stdc++.h>
using namespace std;

const int N = 22;

int a[N][N];

bool vis[N][N];

//all four directions
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};
int ans, n;

void dfs(int i, int j)
{

    //mark as visited
    vis[i][j] = 1;

    //if we reach to the destination
    if (i == n && j == n)
        ans++;

    for (int z = 0; z < 4; z++)
    {
        int x = i + dx[z], y = j + dy[z];

        //check for valid cell
        if (x >= 1 && x <= n and y >= 1 && y <= n)
        {

            //if not visited and value is 0
            //then call for dfs
            if (!a[x][y] and !vis[x][y])
                dfs(x, y);
        }
    }

    //mark as unvisited (backtrack)
    vis[i][j] = 0;
}

int main()
{

    ans = 0;

    n = 4;
    vector<vector<int>> arr = {{0, 1, 1, 0},
                               {0, 0, 1, 0},
                               {0, 0, 0, 0},
                               {0, 1, 1, 0}};

    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            a[i][j] = arr[i - 1][j - 1];
        }
    }
    dfs(1, 1);

    cout << ans << "\n";

    return 0;
}