982. Connectivity

 

Check if the given undirected graph is connected. That is, determine whether it is possible to reach any vertex from any other vertex using the edges of the graph.

 

Input. The first line contains two numbers: n (1 ≤ n ≤ 100) – the number of vertices, and m (1 ≤ m ≤ 104) – the number of edges in the graph. Each of the following m lines contains two numbers ui and vi (1 ≤ ui, vi ≤ n), representing an edge between vertices ui and vi.

 

Output. Print “YES”, if the graph is connected, and “NO” otherwise.

 

Sample input 1

Sample output 1

3 2

1 2

3 2

YES

 

 

Sample input 2

Sample output 2

3 1

1 3

NO

 

 

SOLUTION

depth first search

 

Algorithm analysis

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 realization

Declare the adjacency matrix g and the array of visited vertices used.

 

#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 cnt.

 

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 realization – the number of visited vertices

Declare the adjacency matrix g and the array of visited vertices used.

 

#define MAX 101

int g[MAX][MAX], used[MAX];

 

The dfs function performs a depth-first search starting from vertex v. The variable cnt 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);

}

 

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 realization – 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 x1 and y1​. If x1 = y1​, then x and y are already in the same set, and no further action is needed. Otherwise, we redirect the pointer of representative x1 to y1.

 

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 (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 count. 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 count variable, print the result.

 

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

else printf("NO\n");

 

Python realization

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 cnt.

 

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 realization – the number of visited vertices

The dfs function performs a depth-first search starting from vertex v. The variable cnt 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)

 

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 realization – disjoint sets union

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).

 

def Repr(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 x1 and y1​. If x1 = y1​, then x and y are already in the same set, and no further action is needed. Otherwise, we redirect the pointer of representative x1 to y1.

 

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 (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 the number of connected components in the variable count. 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 in range(1, n + 1):

  if mas[i] == i:

    count += 1

 

Based on the value of the count variable, print the result.

 

if count == 1:

  print("YES")

else:

  print("NO")