2472. Операции на графе

 

В задаче необходимо создать неориентированный граф, на котором поддерживаются следующие операции:

1.     AddEdge(u, v) – добавить в граф ребро между вершинами (u, v);

2.     Vertex(u) – вывести список вершин, смежных с вершиной u.

Петель и кратных ребер в графе нет.

 

Вход. В первой строке содержится количество вершин в графе n (1 ≤ n ≤ 105). В следующей строке находится количество операций k (0 ≤ k ≤ 106). Каждая из следующих строк задает операцию в формате: "1 <число> <число>" или "2 <число>", обозначающие соответственно операции AddEdge(u, v) и Vertex(u).

Гарантируется, что суммарное количество чисел, которое необходимо вывести при выполнении всех операций Vertex, не превосходит 2 * 105.

 

Выход. Для каждой команды Vertex вывести в отдельной строке список смежных вершин указанной вершины. Вершины списка смежности можно выводить в произвольном порядке. Если для указанной вершины смежных нет, то следует вывести пустую строку.

 

Пример входа

Пример выхода

4

4

1 1 2

1 2 3

2 4

2 2

3 1

 

 

РЕШЕНИЕ

графы

 

Анализ алгоритма

Граф будем хранить при помощи списка смежности вершин g. При поступлении операции AddEdge добавляем неориентированное ребро (u, v) в граф. При поступлении операции Vertex выводим текущее содержимое динамического массива g[u].

 

Пример

Граф, приведенный в примере, имеет вид:

 

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

Граф будем хранить в виде списка смежности.

 

vector<vector<int> > g;

 

Читаем входные данные.

 

scanf("%d %d",&n,&k);

g.resize(n+1);

 

Для каждой строки читаем код операции в переменную c.

 

while(k--)

{

  scanf("%d",&c);

 

Если это операция AddEdge, то добавляем неориентированное ребро (u, v) в граф.

 

  if (c == 1)

  {

    scanf("%d %d",&u,&v);

    g[u].push_back(v); g[v].push_back(u);

  } else

 

Иначе выводим список вершин, смежных с вершиной u. Для этого следует вывести все содержимое динамического массива g[u].

 

  {

    scanf("%d",&u);

    for (i = 0; i < g[u].size(); i++)

      printf("%d ", g[u][i]);

Выводим символ перехода на новую строку. Если g[u] пусто, то фактически будет выведена пустая строка.

 

    printf("\n");

  }

}

 

Java реализация

 

import java.util.*;

//import java.io.*;

 

public class Main

{

  public static void main(String[] args) // throws IOException

  {

    //Scanner con = new Scanner(new FileReader ("2472.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>());

   

    int k = con.nextInt();

    while(k-- > 0)

    {

      int c = con.nextInt();

      if (c == 1)

      {

        int u = con.nextInt();

        int v = con.nextInt();

        g.get(u).add(v); g.get(v).add(u);

      } else

      {

        int u = con.nextInt();

        for(int i = 0; i < g.get(u).size(); i++)

          System.out.print(g.get(u).get(i) + " ");             

        System.out.println();

      }

    }

    con.close();

  }

}

 

Java реализация – массив ArrayList

 

import java.util.*;

//import java.io.*;

 

public class Main

{

  public static void main(String[] args) // throws IOException

  {

    //Scanner con = new Scanner(new FileReader ("2472.in"));

    Scanner con = new Scanner(System.in);

   

    int n = con.nextInt();

    ArrayList<Integer>[] g = new ArrayList[n+1];

    for (int i = 0; i <= n; i++)

      g[i] = new ArrayList<Integer>();

   

    int k = con.nextInt();

    while(k-- > 0)

    {

      int c = con.nextInt();

      if (c == 1)

      {

        int u = con.nextInt();

        int v = con.nextInt();

        g[u].add(v); g[v].add(u);

      } else

      {

        int u = con.nextInt();

        for(int i = 0; i < g[u].size(); i++)

          System.out.print(g[u].get(i) + " ");            

        System.out.println();

      }

    }

    con.close();

  }

}