Від матриці суміжності до списків суміжності#3981

Від матриці суміжності до списків суміжності (Розбір)

Читаємо матрицю суміжності та будуємо за нею список суміжності. Потім виводимо його.

Приклад

Граф з прикладу має наступний вигляд.

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

Оголошуємо список суміжності графа.

vector<vector<int> > g;

Читаємо вхідні дані. Вершини графа нумеруються від $1$ до $n$ . Будуємо список суміжності.

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

Виводимо список суміжності.

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

C++

Java реалізація — array of ArrayList

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 реалізація — 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 реалізація

Читаємо кількість вершин $n$ . Оголошуємо список суміжності $g$ .

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

Читаємо матрицю суміжності та будуємо список суміжності. Вершини графа нумеруються від $1$ до $n$ .

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)

Виводимо список суміжності.

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