Повний граф#3987

Повний граф (Розбір)

Нехай $A$ — матриця суміжності. Граф є повним, якщо у всіх клітинках матриці $A$ , крім діагональних, знаходяться одиниці.

Приклад

Граф, наведений у прикладі, має вигляд:

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

Матрицю суміжності графа зберігаємо в масиві $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;
}

C++

Перебираємо елементи матриці, розташовані над головною діагоналлю. Якщо всі вони дорівнюють $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();
  }
}

Java

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