982. Connectivity

 

Check whether the given undirected graph is connected. That its possible to go from any vertex to any other along the edges of this graph.

 

Input. The first line contains the numbers n and m are separated by spaces – the number of vertices in the graph, respectively (1 ≤ n ≤ 100, 1 ≤ m ≤ 10000). The following m lines contain two numbers ui and vi by a space (1 ≤ ui, vi ≤ n); each such line means that the graph there is 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 the depth first search we calculate the number of connected components. If this number is 1, the graph is connected.

Second way to solve the problem is to start the depth first search from vertex 1 and calculate the number of visited vertices. If it is n, the graph is connected.

 

Example

Graphs given in example, have the form:

 

Algorithm realization

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

 

#define MAX 101

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

 

Depth first search from the vertex v.

 

void dfs(int v)

{

  used[v] = 1;

  for (int i = 1; i <= n; i++)

    if (g[v][i] && !used[i]) dfs(i);

}

 

Read the input data.

 

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

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

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

 

for(i = 0; i < m; i++)

{

  scanf("%d %d",&a,&b);

  g[a][b] = g[b][a] = 1;

}

 

Calculate the number of connected components in the variable cnt.

 

cnt = 0;

for(i = 1; i <= n; i++)

  if (!used[i])

  {

    dfs(i);

    cnt++;

  }

 

If graph contains only one connected component, it is connected.

 

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

else printf("NO\n");

 

Algorithm realization – the number of visited vertices

 

#include <stdio.h>

#include <string.h>

#define MAX 101

 

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

int cnt, n, m, i, a, b;

 

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

}

 

int main(void)

{

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

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

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

 

  for(i = 0; i < m; i++)

  {

    scanf("%d %d", &a, &b);

    g[a][b] = g[b][a] = 1;

  }

 

  cnt = 0;

  dfs(1);

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

  else printf("NO\n");

  return 0;

}

 

Algorithm realization – disjoint sets union

 

#include <stdio.h>

#define MAX 102

 

int mas[MAX];

 

int Repr(int n)

{

  while (n != mas[n]) n = mas[n];

  return n;

}

 

void Union(int x, int y)

{

  int x1 = Repr(x), y1 = Repr(y);

  if (x1 == y1) return;

  mas[x1] = y1;

}

 

int i, j, n, m, a, b, count;

 

int main(void)

{

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

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

 

  for (i = 1; i <= m; i++)

  {

    scanf("%d %d", &a, &b);

    Union(a, b);

  }

 

  count = 0;

  for (i = 1; i <= n; i++)

    if (mas[i] == i) count++;

 

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

  else printf("NO\n");

 

  return 0;

}