Разбор

Пусть $А$ — матрица смежности. Граф является полным, если во всех ячейках матрицы $А$ кроме диагональных находятся единицы.

Пример

Граф, приведенный в примере, имеет вид:

Реализация алгоритма

Матрицу смежности графа храним в массиве $g$ .

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

Читаем входные данные. Строим матрицу смежности графа.

scanf("%d %d",&n,&m);
memset(g,0,sizeof(g));

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

Перебираем элементы матрицы, расположенные над главной диагональю. Если все они равны $1$ , то по окончанию цикла переменная $f l a g$ будет содержать $1$ . Если хотя бы один элемент матрицы равен $0$ , то граф не является полным, $f l a g$ будет установлен в $0$ .

flag = 1; // complete graph
for(i = 1; i <= n; i++)
for(j = i + 1; j <= n; j++)
  if (g[i][j] == 0) flag = 0;

Выводим ответ.

if (flag == 1) puts("YES");
else puts("NO");

Java реализация

import java.util.*;

public class Main
{
  public static void main(String[] args)
  {
    Scanner con = new Scanner(System.in);
    int n = con.nextInt();
    int m = con.nextInt();

    int g[][] = new int[n+1][n+1];
    for(int i = 0; i < m; i++)
    {
      int a = con.nextInt();
      int b = con.nextInt();
      g[a][b] = g[b][a] = 1;
    }
    	
    int res = 1;
    for(int i = 1; i <= n; i++)
    for(int j = i + 1; j <= n; j++)
      if (g[i][j] == 0) res = 0;

    if (res == 1)
      System.out.println("YES");
    else
      System.out.println("NO");    	
    con.close();
  }
}

Python реализация

Читаем количество вершин $n$ и количество рёбер $m$ графа.

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

Читаем список смежности. Строим матрицу смежности графа $g$ .

g = [[0] * (n + 1) for _ in range(n + 1)]
for _ in range(m):
  a, b = map(int, input().split())
  g[a][b] = g[b][a] = 1

flag = 1
for i in range(1, n + 1):
  for j in range(i + 1, n + 1):
    if g[i][j] == 0: flag = 0

Выводим ответ.

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