# 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 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 $x_{1}$ and $y_{1}$. If $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}$ to $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 ($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 $x_{1}$ and $y_{1}$. If $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}$ to $y_{1}$.

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