Matt's Graph Book

--------------------------------------------------------------------------------------------------------
                                                #Python Solution
--------------------------------------------------------------------------------------------------------
import resource
import sys
resource.setrlimit(resource.RLIMIT_STACK, [0x10000000, resource.RLIM_INFINITY])
sys.setrecursionlimit(0x10000001)

def dfs(u):
    visited[u] = 1
    for i in range(len(adj[u])):
        v = adj[u][i]
        if not visited[v]:
            dfs(v)
           
n = int(input())
m = int(input())
adj = []
visited = [0]*(n+1)
for _ in range(n+1): adj.append([])
for i in range(m):
    x,y = map(int,input().split())
    adj[x].append(y)
    adj[y].append(x)
d = int(input())
adj[d].clear()
dfs(1)
ans = 1
for i in range(n):
    if not visited[i]:
        ans = 0
        break
print("Connected" if ans else "Not Connected")
           

--------------------------------------------------------------------------------------------------------
                                                # C++ Solution
---------------------------------------------------------------------------------------------------------------------------------------------------

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

vector< int >adj[1000001];
vector< bool >visited(1000001,false);

void dfs(int u)
{
    visited[u] = true;
    for(int i = 0; i < adj[u].size() ; i++){
        int v = adj[u][i];
        if(visited[v] == false)
            dfs(v);
    }
}
int main()
{
    int n,m,x,y,d;
    cin >> n >> m;
    for(int i = 0; i < m ; i++){
        cin >> x >> y;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }
    cin >> d;
    adj[d].clear();
    dfs(1);
    bool ans  = true;
    for(int i = 0; i < n ; i++){
        if(visited[i] == false){
            ans = false;
            break;
        }
    }
    cout << ((ans)? "Connected" : "Not Connected" ) << endl;
    return 0;
}

Feasible relations

--------------------------------------------------------------------------------------------------------
                                                #Python Solution
--------------------------------------------------------------------------------------------------------

import resource
import sys
resource.setrlimit(resource.RLIMIT_STACK, [0x10000000, resource.RLIM_INFINITY])
sys.setrecursionlimit(0x10000001)

def find(i):
    if(subset[i] != i):
        subset[i] = find(subset[i])
    return subset[i]

def UnionSet(x,y):
    xroot = find(x)
    yroot = find(y)
    subset[xroot] = yroot
   
t = int(input())
for _ in range(t):
    n,m = map(int,input().split())
    subset = [0]*(n+1)
    for i in range(n):
        subset[i] = i
   
    ans = 0
    for i in range(m):
        x,op,y = input().split(' ')
        x = int(x) - 1
        y = int(y) - 1
        if op == "=":
            UnionSet(x,y)
        elif find(x) == find(y):
            ans = 1
    print('YES' if not ans else 'NO')
           
 
--------------------------------------------------------------------------------------------------------
                                                # C++ Solution
--------------------------------------------------------------------------------------------------------

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

struct subset{
    int parent ,rank ;
};

int find(struct subset subsets[],int i){
    if(subsets[i].parent != i) subsets[i].parent = find(subsets,subsets[i].parent);
    return subsets[i].parent;
}

void UnioSet(struct subset subsets[], int x, int y)
{
    int xroot = find(subsets,x);
    int yroot = find(subsets,y);

    if(subsets[xroot].rank < subsets[yroot].rank)subsets[xroot].parent = yroot;
    else if(subsets[xroot].rank > subsets[yroot].rank) subsets[yroot].parent = xroot;
    else{
        subsets[yroot].parent = xroot;
        subsets[xroot].rank++;
    }
}

int main()
{
    int t,n,m;
    cin >> t;
    while(t--){
            int x,y;
            string op ;
        cin >> n >> m;
        struct subset* subsets = (struct subset*) malloc((n+1)* sizeof(struct subset));
        for(int i = 0; i < n ; i++){
            subsets[i].parent = i;
            subsets[i].rank = 0;
        }
        int ans = 0;
        for(int i = 0; i < m; i++){
            cin >> x >>  op >> y;
            if(op == "=")
                UnioSet(subsets,x,y);
            else if(find(subsets,x) == find(subsets,y)) ans = 1;
        }


      cout << ((ans == 1)? "NO\n" : "YES\n");
    }
    return 0;
}
 

Monk and Graph Problem

# Python Solution
 
import resource
import sys
sys.setrecursionlimit(0x100000)
#if you don't write this line you got runtime error ,coz python recursionlimit is soo poor , so you need upgrade recursionlimit
# Will segfault without this line.
#resource.setrlimit(resource.RLIMIT_STACK, [0x10000000, resource.RLIM_INFINITY])

def find_component(u):
    global ans
    if component[u] != -1:
        return
       
    component[u] = 0
       
    for i in range(0,len(adj[u])):
        ans += 1
        find_component(adj[u][i])
           
           
n,m = map(int,input().split())
adj = []
component = [-1]*(100001)
for i in range(n+1): adj.append([])
for i in range(m):
    x,y = map(int,input().split())
    adj[x].append(y)
    adj[y].append(x)
res = 0
for i in range(1,n+1):
    ans = 0
    if (component[i] == -1):
        find_component(i)
        res = max(res,ans//2)
           
print(res)

#C++ Solution

#include< bits/stdc++.h >
using namespace std;
vector< int >adj[100001];
vector< int >component(100001,-1);
int n,ans = 0;
void find_component(int u)
{

    if (component[u] == 0) {
        return ;
    }
    component[u] = 0;

    for(int i = 0; i < adj[u].size() ; i++){
        ans++;
        find_component(adj[u][i]);
    }

}

int main()
{
    int m,x,y;
    cin >> n >> m;
    for(int i = 0; i < m; i++){
        cin >> x >> y;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }
    int components = 0,res = 0;
    for(int i = 1; i <= n; i++){
        ans = 0;
        if(component[i] == -1){
            find_component(i);
            // component++ if need how many component graph are present
        res = max(res,ans/2);
        }
    }
    cout << res << endl;
    return 0;
}
 
 

Happy Vertices (Python3)

def dfs(u):
    global ans
    for i in range(len(adj[u])):
        v = adj[u][i]
        if not visited[v]:
            visited[v] = len(adj[v])-1
            if visited[v] > visited[u]:
                ans += 1
            dfs(v)



n,m = map(int,input().split())
ans = 0
adj = []
for i in range(n+1): adj.append([])
for i in range(m):
    x,y = map(int,input().split())
    adj[x].append(y)
    adj[y].append(x)

visited = [0]*(n+1)
for i in range(1,n+1):
    if not visited[i]:
        visited[i] = len(adj[i])
        dfs(i)
print(ans)

Prison Break (Python3)

n = 0
def recursive(u,v):
    global ans
    if(u == n-1 and v == n-1):
        ans += 1
        return
    data[u][v] = 1

    if(u-1 >= 0 and data[u-1][v] == 0):
         recursive(u-1,v)
    if(u+1 < n and data[u+1][v] == 0):
        recursive(u+1,v)
    if(v-1 >= 0 and data[u][v-1] == 0):
         recursive(u,v-1)
    if(v+1 < n and data[u][v+1] == 0):
         recursive(u,v+1)
    data[u][v] = 0
   
    return
   
   
t = int(input())
for _ in range(t):
    n = int(input())
    data = []
    for i in range(n):
        data.append(list(map(int,input().split())))
    ans = 0
    recursive(0,0)
    print(ans)

Prison Break

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

int data[21][21];

int dfs(int u,int v,int n){
    int ans = 0;

    if( u == n and v == n) return 1;
    data[u][v] = 1;
    if(u - 1 >= 1 and data[u-1][v] == 0)
         ans += dfs(u-1,v,n);
    if(v - 1 >= 1 and data[u][v-1] == 0)
         ans += dfs(u,v-1,n);
    if(u+1 <= n and data[u+1][v] == 0)
         ans += dfs(u+1,v,n);
    if(v+1 <= n and data[u][v+1] == 0)
         ans += dfs(u,v+1,n);
    data[u][v] = 0;
 return ans ;
}
int main()
{
    freopen("in.txt","r",stdin);
    int n, t;
    cin >> t;
    while(t--){
    cin >> n;

    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
           cin >> data[i][j];

    if(data[1][1] == 1 and data[n][n] == 1) cout << 0 << endl;
    else cout << dfs(1,1,n) << endl;

    }
    return 0;
}

Happy Vertices

/*                             Name : Arif Khan
                                Date : 1/3/18
                                Problem Title: Happy Vertices
Problem Link : https://www.hackerearth.com/practice/algorithms/graphs/depth-first-search/practice-problems/algorithm/happy-vertices/

*/

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

vector < int >adj[100001];
vector < int > visited(100001,0);
int ans = 0;

void dfs(int u){

    for(int i = 0; i < adj[u].size() ; i++){
        int v = adj[u][i];
        if(visited[v] == 0){
                visited[v] = adj[v].size() - 1;
            if(visited[v] > visited[u]) ans++;
            dfs(v);
        }
    }
}

int main()
{
    int n , m , x , y;
    cin >> n >> m;
    for(int i = 1; i <= m ; i++){
        cin >> x >> y;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }
    for(int i = 1; i <= n; i++){
        if(visited[i] == 0){
            visited[i] = adj[i].size();
            dfs(i);
        }
    }
    cout << ans << endl;
    return 0;
}