Connectivity (Editorial)

Using depth-first search, we can calculate the number of connected components. If it equals $1$ , the graph is connected.

Another solution is to start a depth-first search from vertex $1$ and count the number of visited vertices. If it equals $n$ , the graph is connected.

Example

Graphs given in example, have the form:

Algorithm implementation

Declare the adjacency matrix $g$ and the array of visited vertices $u se d$ .

#define MAX 101
int g[MAX][MAX], used[MAX];

The dfs function performs a depth-first search starting from vertex $v$ .

void dfs(int v)
{
  used[v] = 1;
  for (int i = 1; i <= n; i++)
    if (g[v][i] && !used[i]) dfs(i);
}

The main part of the program. Read the input data.

scanf("%d %d", &n, &m);

Initialize the arrays.

memset(g,0,sizeof(g)); 
memset(used,0,sizeof(used));

Сonstruct the adjacency matrix of the graph.

for (i = 0; i < m; i++)
{
  scanf("%d %d", &a, &b);
  g[a][b] = g[b][a] = 1;
}

The number of connected components is stored in the variable $c n t$ .

cnt = 0;

Start a depth-first search on a disconnected graph.

for (i = 1; i <= n; i++)
  if (!used[i]) 
  {

The number of dfs function calls equals the number of connected components in the graph.

    dfs(i);
    cnt++;
  }

Print the result. If the graph has only one connected component, it is connected.

if (cnt == 1) printf("YES\n");
else printf("NO\n");

Algorithm implementation — the number of visited vertices

Declare the adjacency matrix $g$ and the array of visited vertices $u se d$ .

#define MAX 101
int g[MAX][MAX], used[MAX];

The dfs function performs a depth-first search starting from vertex $v$ . The variable $c n t$ keeps track of the number of visited vertices.

void dfs(int v)
{
  used[v] = 1;
  cnt++;
  for (int i = 1; i <= n; i++)
    if ((g[v][i] == 1) && (used[i] == 0)) dfs(i);
}

C++

The main part of the program. Read the input data.

scanf("%d %d", &n,&m);

Initialize the arrays.

memset(g, 0, sizeof(g)); 
memset(used, 0, sizeof(used));

Сonstruct the adjacency matrix of the graph.

for (i = 0; i < m; i++)
{
  scanf("%d %d", &a, &b);
  g[a][b] = g[b][a] = 1;
}

Start a depth-first search from vertex $1$ .

cnt = 0;
dfs(1);

If the depth-first search visits all $n$ vertices, then the graph is connected.

if (cnt == n) printf("YES\n");
else printf("NO\n");

Algorithm implementation — disjoint sets union

Declare an array.

#define MAX 102
int mas[MAX];

The Repr function returns the representative of the set that contains vertex $n$ . We move along the pointer to the next element until we encounter the representative of the set (whose pointer points to itself).

int Repr(int n)
{
  while (n != mas[n]) n = mas[n];
  return n;
}

The Union function merges two sets containing vertices $x$ and $y$ . Find the representatives of the sets containing $x$ and $y$ . Let these representatives be $x_{1}$ x_1 and $y_{1}$ y_1. If $x_{1} = y_{1}$ x_1 = y_1, then $x$ and $y$ are already in the same set, and no further action is needed. Otherwise, we redirect the pointer of representative $x_{1}$ x_1 to $y_{1}$ y_1.

void Union(int x, int y)
{
  int x1 = Repr(x), y1 = Repr(y);
  if (x1 == y1) return;
  mas[x1] = y1;
}

The main part of the program. Read the input data.

scanf("%d %d", &n, &m);

Initially, each vertex points to itself ( $ma s [i] = i$ mas[i] = i).

for (i = 1; i <= n; i++) mas[i] = i;

Read the edges of the graph. For each edge $(a, b)$ , perform the union of the sets containing vertices $a$ and $b$ .

for (i = 1; i <= m; i++)
{
  scanf("%d %d", &a, &b);
  Union(a, b);
}

Count the number of connected components in the variable $co u n t$ . This number equals the number of vertices that are representatives of their own sets (i.e., the vertices whose pointers point to themselves).

count = 0;
for (i = 1; i <= n; i++)
  if (mas[i] == i) count++;

Based on the value of the $co u n t$ variable, print the result.

if (count == 1) printf("YES\n");
else printf("NO\n");

Python implementation

The dfs function performs a depth-first search starting from vertex $v$ .

def dfs(v):
  used[v] = 1
  for i in range(1, n + 1):
    if g[v][i] and not used[i]:
      dfs(i)

The main part of the program. Read the input data.

n, m = map(int, input().split())

Initialize the lists.

g = [[0] * (n + 1) for _ in range(n + 1)]
used = [0] * (n + 1)

Сonstruct the adjacency matrix of the graph.

for i in range(m):
  a, b = map(int, input().split())
  g[a][b] = g[b][a] = 1

The number of connected components is stored in the variable $c n t$ .

cnt = 0

Start a depth-first search on a disconnected graph.

for i in range(1, n + 1):
  if not used[i]:

The number of dfs function calls equals the number of connected components in the graph.

    dfs(i)
    cnt += 1

Print the result. If the graph has only one connected component, it is connected.

if cnt == 1:
  print("YES")
else:
  print("NO")

Python implementation — the number of visited vertices

The dfs function performs a depth-first search starting from vertex $v$ . The variable $c n t$ keeps track of the number of visited vertices.

def dfs(v):
  used[v] = 1
  global cnt
  cnt += 1
  for i in range(1, n + 1):
    if g[v][i] and not used[i]:
      dfs(i)

Python

The main part of the program. Read the input data.

n, m = map(int, input().split())

Initialize the lists.

g = [[0] * (n + 1) for _ in range(n + 1)]
used = [0] * (n + 1)

Сonstruct the adjacency matrix of the graph.

for i in range(m):
  a, b = map(int, input().split())
  g[a][b] = g[b][a] = 1

Start a depth-first search from vertex $1$ .

cnt = 0
dfs(1)

If the depth-first search visits all $n$ vertices, then the graph is connected.

if cnt == n:
  print("YES")
else:
  print("NO")

Python implementation — disjoint sets union

def Repr(n):
  while n != mas[n]:
    n = mas[n]
  return n

def Union(x, y):
  x1 = Repr(x)
  y1 = Repr(y)
  if x1 == y1: return
  mas[x1] = y1

The main part of the program. Read the input data.

n, m = map(int, input().split())

Initially, each vertex points to itself ( $ma s [i] = i$ mas[i] = i).

mas = [0] * (n + 1)
for i in range(1, n + 1):
  mas[i] = i

Read the edges of the graph. For each edge $(a, b)$ , perform the union of the sets containing vertices $a$ and $b$ .

for _ in range(m):
  a, b = map(int, input().split())
  Union(a, b)

count = 0
for i in range(1, n + 1):
  if mas[i] == i:
    count += 1

Based on the value of the $co u n t$ variable, print the result.

if count == 1:
  print("YES")
else:
  print("NO")