python3 での実装例を以下に紹介します。

#入力例1
# 6 6
# 1 2
# 1 3
# 2 4
# 3 4
# 4 5
# 4 6

N, M = map(int, input().split())
G = [[] for m in range(M)]
visited = [False] * N #頂点 x が青色の場合, visited[x] = True
for i in range(M):
    a, b = map(int, input().split())
    G[a-1].append(b-1) # 0-index に変更
    G[b-1].append(a-1) # 0-index に変更
#print('G =', G)

def dfs(pos): # posは現在位置
    visited[pos] = True
    for i in range(len(G[pos])):
        nex = G[pos][i]
        if visited[nex] == False:
            dfs(nex)
    return

#深さ優先探索
dfs(1)
# 答えの出力
Answer = 'The graph is connected.'
for i in range(N):
    if visited[i] == False:
        Answer = 'The graph is not connected.'
print(Answer)