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;
}