Qonşuluq matrisindən qonşuluq siyahılarına#3981

Qonşuluq matrisindən qonşuluq siyahılarına (Həll təhlili)

Bitişiklik matrisini oxuyuruq və ondan bitişiklik siyahısını qururuq. Sonra onu çıxış edirik.

Nümunə

Misaldakı qraf aşağıdakı kimidir.

Alqoritmin tətbiqi

Qrafın bitişiklik siyahısını elan edək.

vector<vector<int> > g;

Giriş məlumatlarını oxuyuruq. Qrafın zirvələri $1$ -dən $n$ -ə qədər nömrələnir. Bitişiklik siyahısını qururuq.

scanf("%d", &n);
g.resize(n + 1);
for (i = 1; i <= n; i++)
for (j = 1; j <= n; j++)
{
  scanf("%d", &val);
  if (val) g[i].push_back(j);
}

C++

Bitişiklik siyahısını çıxış edirik.

for (i = 1; i <= n; i++)
{
  printf("%d", g[i].size());
  for (int x : g[i])
    printf(" %d", x);
  printf("\n");
}

C++

Java tətbiqi — ArrayList array-i

import java.util.*;

public class Main
{
  public static void main(String[] args)
  {
    Scanner con = new Scanner(System.in);
    
    int n = con.nextInt();
    ArrayList<Integer>[] g = new ArrayList[n+1]; // unchecked
    for (int i = 0; i <= n; i++)
      g[i] = new ArrayList<Integer>();
    
    for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++)
    {
      int val = con.nextInt();
      if (val == 1) g[i].add(j);
    }

    for (int i = 1; i <= n; i++)
    {
      System.out.print(g[i].size());
      for (int j = 0; j < g[i].size(); j++)
        System.out.print(" " + g[i].get(j));
      System.out.println();
    }
    con.close();
  }
}

Java

Java tətbiqi — ArrayList of ArrayList

import java.util.*;
import java.io.*;

public class Main
{
  public static void main(String[] args)  throws IOException
  {
    //Scanner con = new Scanner(new FileReader ("3981.in"));
    Scanner con = new Scanner(System.in);
    
    int n = con.nextInt();
    ArrayList<ArrayList<Integer>> g = 
      new ArrayList<ArrayList<Integer>>();
    for (int i = 0; i <= n; i++)
      g.add(new ArrayList<Integer>());
    
    for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++)
    {
      int val = con.nextInt();
      if (val == 1) g.get(i).add(j);
    }

    //System.out.println(g);
    
    for (int i = 1; i <= n; i++)
    {
      System.out.print(g.get(i).size());
      for (int j = 0; j < g.get(i).size(); j++)
        System.out.print(" " + g.get(i).get(j));
      System.out.println();
    }
    con.close();
  }
}

Java

Python tətbiqi

Zirvə sayını $n$ oxuyuruq. Bitişiklik siyahısını $g$ elan edək.

n = int(input())
g = [[] for _ in range(n + 1)]

Bitişiklik matrisini oxuyuruq və bitişiklik siyahısını qururuq. Qrafın zirvələri $1$ -dən $n$ -ə qədər nömrələnir.

for i in range(1, n + 1):
  row = list(map(int, input().split()))
  for j in range(1, n + 1):
    if row[j - 1]:
      g[i].append(j)

Bitişiklik siyahısını çıxış edirik.

for i in range(1, n + 1):
  print(len(g[i]), *g[i])