Tam qraf#3987

Tam qraf (Həll təhlili)

Verilmiş $A$ — uyğunluq matrisasıdır. Qraf tamdır, əgər $A$ matrisasında diaqonal olan hüceyrələr istisna olmaqla, qalan bütün hüceyrələrdə birlər yerləşirsə.

Misal

Misalda verilmiş qraf belə görünür:

Alqoritmin həyata keçirilməsi

Qrafın uyğunluq matrisasını $g$ massivində saxlayırıq.

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

Giriş məlumatlarını oxuyuruq. Qrafın uyğunluq matrisasını qururuq.

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++

Əsas diaqonaldan yuxarı yerləşən matris elementlərini yoxlayırıq. Əgər onların hamısı $1$ -ə bərabərdirsə, o zaman yoxlamanın sonunda $f l a g$ dəyişəni $1$ -i saxlayacaq. Əgər matrisdə ən azı bir element $0$ -dırsa, qraf tam deyil və $f l a g$ $0$ -a bərabər olacaq.

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

Cavabı veririk.

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

Java həyata keçirilməsi

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 həyata keçirilməsi

Qrafın $n$ vertexləri və $m$ qıraqları sayını oxuyuruq.

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

Uyğunluq siyahısını oxuyuruq. Qrafın uyğunluq matrisasını $g$ ilə qururuq.

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

Cavabı veririk.

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