Grade 11 · Undirected graphsCitește în română

Checking a path (chain)

Original: Verificarea unui lanț

O(n²)C++17114 lines3 examples

The idea

A sequence of nodes x1, x2, ..., xk is a path if any two consecutive nodes are joined by an edge; the length of the path is k - 1 (the number of edges). The path is elementary if its nodes are distinct and simple if the edges used are distinct (every elementary path is also simple). We check in turn: the consecutive edges, then repeated nodes (a frequency array), then repeated edges (a matrix of used edges). Input: n m, the m edges, then k and the k nodes.

Original description (Romanian)

O succesiune de noduri x1, x2, ..., xk este lanț dacă oricare două noduri consecutive sunt unite printr-o muchie; lungimea lanțului este k - 1 (numărul de muchii). Lanțul este elementar dacă nodurile sunt distincte și simplu dacă muchiile folosite sunt distincte (orice lanț elementar este și simplu). Se verifică pe rând: muchiile consecutive, apoi nodurile repetate (vector de frecvență), apoi muchiile repetate (o matrice de muchii folosite). Datele: n m, cele m muchii, apoi k și cele k noduri.

Complexity
O(n² + k)
Grade
Grade 11 (Clasa a XI-a)

Examples

Example 1

Input

5 6
1 2
2 3
3 4
4 1
2 5
4 5
5
1 2 5 4 3

Expected output

Lant de lungime 4
Elementar: DA
Simplu: DA
Example 2

Input

5 6
1 2
2 3
3 4
4 1
2 5
4 5
6
2 1 4 5 2 3

Expected output

Lant de lungime 5
Elementar: NU
Simplu: DA
Example 3

Input

5 6
1 2
2 3
3 4
4 1
2 5
4 5
3
1 3 4

Expected output

Nu este lant

The code

Comments are in Romanian, as in the original collection. Edit freely: you can reset at any time.

verificarea-unui-lant.cpp
/*
 * Titlu: Verificarea unui lanț
 * Clasa: 11
 * Capitol: Grafuri neorientate
 * Descriere: O succesiune de noduri x1, x2, ..., xk este lanț dacă oricare două noduri
 *            consecutive sunt unite printr-o muchie; lungimea lanțului este k - 1 (numărul
 *            de muchii). Lanțul este elementar dacă nodurile sunt distincte și simplu dacă
 *            muchiile folosite sunt distincte (orice lanț elementar este și simplu). Se
 *            verifică pe rând: muchiile consecutive, apoi nodurile repetate (vector de
 *            frecvență), apoi muchiile repetate (o matrice de muchii folosite). Datele:
 *            n m, cele m muchii, apoi k și cele k noduri.
 * Complexitate: O(n² + k)
 *
 * Exemplu
 * Intrare:
 * 5 6
 * 1 2
 * 2 3
 * 3 4
 * 4 1
 * 2 5
 * 4 5
 * 5
 * 1 2 5 4 3
 * Ieșire:
 * Lant de lungime 4
 * Elementar: DA
 * Simplu: DA
 *
 * Exemplu
 * Intrare:
 * 5 6
 * 1 2
 * 2 3
 * 3 4
 * 4 1
 * 2 5
 * 4 5
 * 6
 * 2 1 4 5 2 3
 * Ieșire:
 * Lant de lungime 5
 * Elementar: NU
 * Simplu: DA
 *
 * Exemplu
 * Intrare:
 * 5 6
 * 1 2
 * 2 3
 * 3 4
 * 4 1
 * 2 5
 * 4 5
 * 3
 * 1 3 4
 * Ieșire: Nu este lant
 */
#include <iostream>
using namespace std;

int a[105][105], x[1005], aparitii[105];
bool folosita[105][105];

int main()
{
    int n, m, k;
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        int u, v;
        cin >> u >> v;
        a[u][v] = a[v][u] = 1;
    }
    cin >> k;
    for (int i = 1; i <= k; i++)
    {
        cin >> x[i];
    }

    for (int i = 1; i < k; i++)
    {
        if (a[x[i]][x[i + 1]] == 0)
        {
            cout << "Nu este lant\n";
            return 0;
        }
    }

    bool elementar = true, simplu = true;
    for (int i = 1; i <= k; i++)
    {
        aparitii[x[i]]++;
        if (aparitii[x[i]] > 1)
        {
            elementar = false;
        }
    }
    for (int i = 1; i < k; i++)
    {
        int u = x[i], v = x[i + 1];
        if (folosita[u][v])
        {
            simplu = false;
        }
        folosita[u][v] = folosita[v][u] = true;
    }

    cout << "Lant de lungime " << k - 1 << '\n';
    cout << "Elementar: " << (elementar ? "DA" : "NU") << '\n';
    cout << "Simplu: " << (simplu ? "DA" : "NU") << '\n';
    return 0;
}

Runs on a real g++ (C++17, -O2) through Compiler Explorer. Keep runs short; there's a time limit.