Решение задачи на языке C++/Python G в области программирования. Ограничения по времени для тестирования - 1.5 секунды

Для решения данной задачи на языке программирования C++/Python, мы можем использовать алгоритмы обхода графов. Предлагаю использовать алгоритм обхода в глубину (DFS) для решения этой задачи.

Шаг 1: Создаем структуру данных для хранения графа. В данном случае граф будет представлен в виде списка смежности, где каждая вершина представлена в виде номера.

Шаг 2: Считываем входные данные, включая информацию о количестве вершин и ребер графа, а также информацию о родительских вершинах. Создаем граф на основе этих данных.

Шаг 3: Реализуем функцию DFS, которая будет обходить граф в глубину, начиная с корневой вершины.

Шаг 4: Внутри функции DFS, мы можем рекурсивно вызывать функцию DFS для каждого дочернего узла текущей вершины. Также, мы можем добавить проверку на то, является ли текущая вершина последней (листовой) вершиной графа. Если является, то увеличиваем счетчик листовых вершин.

Шаг 5: Возвращаем из функции DFS значение счетчика листовых вершин.

Шаг 6: В основной программе вызываем функцию DFS для корневой вершины графа и выводим результат.

Пример кода на языке C++:

c++

#include 

#include 



using namespace std;



// Структура для хранения графа

struct Graph {

    int V; // Количество вершин

    vector> adj; // Список смежности

};



// Создание новой вершины графа

vector> createGraph(int V) {

    // Создаем граф с V вершинами

    vector> adj(V);

    return adj;

}



// Добавление ребра в граф

void addEdge(vector>& adj, int u, int v) {

    // Добавляем ребро u -> v

    adj[u].push_back(v);

}



// Функция обхода в глубину

int DFS(vector>& adj, int v) {

    int count = 0;

    if (adj[v].size() == 0) {

        return 1;

    }



    // Рекурсивно вызываем DFS для каждого дочернего узла текущей вершины

    for (int i = 0; i < adj[v].size(); i++) {

        count += DFS(adj, adj[v][i]);

    }



    return count;

}



int main() {

    // Чтение входных данных

    int V, E;

    cin >> V >> E;



    // Создание графа

    vector> adj = createGraph(V);



    // Чтение информации о родительских вершинах

    for (int i = 0; i < E; i++) {

        int u, v;

        cin >> u >> v;

        addEdge(adj, u, v);

    }



    // Вызов функции DFS для корневой вершины

    int leafVertices = DFS(adj, 0);



    // Вывод результата

    cout << "Количество листовых вершин: " << leafVertices << endl;



    return 0;

}

Пример кода на языке Python:

python

# Структура для хранения графа

class Graph:

    def __init__(self, V):

        self.V = V # Количество вершин

        self.adj = [[] for _ in range(V)] # Список смежности



    # Добавление ребра в граф

    def addEdge(self, u, v):

        # Добавляем ребро u -> v

        self.adj[u].append(v)



    # Функция обхода графа в глубину (DFS)

    def DFS(self, v):

        count = 1



        if len(self.adj[v]) == 0:

            return 1



        # Рекурсивно вызываем DFS для каждого дочернего узла текущей вершины

        for i in range(len(self.adj[v])):

            count += self.DFS(self.adj[v][i])



        return count



# Чтение входных данных

V, E = map(int, input().split())



# Создание графа

graph = Graph(V)



# Чтение информации о родительских вершинах

for _ in range(E):

    u, v = map(int, input().split())

    graph.addEdge(u, v)



# Вызов функции DFS для корневой вершины

num_leaf_vertices = graph.DFS(0)



# Вывод результата

print(f"Количество листовых вершин: {num_leaf_vertices}")

В обоих примерах мы считываем входные данные, создаем граф, добавляем ребра и вызываем функцию DFS для корневой вершины. Затем выводим количество листовых вершин. Этот код может быть использован для решения данной задачи по обходу графа на языках C++ и Python.