Qonşuluq matrisindən ədədlər siyahısına (Həll təhlili)

Kənarların siyahısını "yerindəcə" çıxaraq, qonşuluq matrisini ardıcıl şəkildə işləyəcəyiq: sətir-sətir yuxarıdan aşağıya qədər, və hər bir sətrin içində — soldan sağa. Qonşuluq matrisindəki hər bir vahid üçün uyğun olan kənarı təyin edən başlara cütlük çıxardırıq. Belə bir keçid zamanı başların cütləri avtomatik olaraq birinci başa görə sıralanır.

Nümunə

Nümunədə verilmiş qraf aşağıdakı görünüşə malikdir:

Alqoritmin həyata keçirilməsi

Qrafın qonşuluq matrisini oxuyuruq. Çünki qraf istiqamətsizdir, yalnız $(i,j)$ kənarları çıxarırıq, burada i < j.

scanf("%d",&n); 
for (i = 1; i <= n; i++)
for (j = 1; j <= n; j++)
{
  scanf("%d",&val);
  if (i < j && val == 1)
    printf("%d %d\n",i,j);
}

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();
    for(int i = 1; i <= n; i++)
    for(int j = 1; j <= n; j++)
    {
      int val = con.nextInt();
      if (i < j && val == 1)
        System.out.println(i + " " + j);
    }
    con.close();
  }
}