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

Isolated nodes and the complete graph

Original: Noduri izolate și graful complet

O(n)C++1773 lines2 examples

The idea

An isolated node has degree 0. A graph is complete if any two distinct nodes are joined by an edge; the complete graph with n nodes has n · (n - 1) / 2 edges and every node has degree n - 1. The program computes the degrees, prints the isolated nodes, says whether the graph is complete and how many edges would still have to be added to make it complete.

Original description (Romanian)

Un nod izolat are gradul 0. Un graf este complet dacă oricare două noduri distincte sunt unite printr-o muchie; graful complet cu n noduri are n · (n - 1) / 2 muchii și fiecare nod are gradul n - 1. Programul calculează gradele, afișează nodurile izolate, spune dacă graful este complet și câte muchii ar mai trebui adăugate ca să devină complet.

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

Examples

Example 1

Input

5 4
1 2
1 3
2 3
3 5

Expected output

Noduri izolate: 4
Complet: NU
Muchii lipsa: 6
Example 2

Input

3 3
1 2
2 3
1 3

Expected output

Noduri izolate: niciunul
Complet: DA
Muchii lipsa: 0

The code

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

noduri-izolate-si-graf-complet.cpp
/*
 * Titlu: Noduri izolate și graful complet
 * Clasa: 11
 * Capitol: Grafuri neorientate
 * Descriere: Un nod izolat are gradul 0. Un graf este complet dacă oricare două noduri
 *            distincte sunt unite printr-o muchie; graful complet cu n noduri are
 *            n · (n - 1) / 2 muchii și fiecare nod are gradul n - 1. Programul calculează
 *            gradele, afișează nodurile izolate, spune dacă graful este complet și câte
 *            muchii ar mai trebui adăugate ca să devină complet.
 * Complexitate: O(n + m)
 *
 * Exemplu
 * Intrare:
 * 5 4
 * 1 2
 * 1 3
 * 2 3
 * 3 5
 * Ieșire:
 * Noduri izolate: 4
 * Complet: NU
 * Muchii lipsa: 6
 *
 * Exemplu
 * Intrare:
 * 3 3
 * 1 2
 * 2 3
 * 1 3
 * Ieșire:
 * Noduri izolate: niciunul
 * Complet: DA
 * Muchii lipsa: 0
 */
#include <iostream>
using namespace std;

int grad[100005];

int main()
{
    long long n, m;
    cin >> n >> m;
    for (long long k = 1; k <= m; k++)
    {
        int x, y;
        cin >> x >> y;
        grad[x]++;
        grad[y]++;
    }

    cout << "Noduri izolate:";
    bool exista = false;
    for (int i = 1; i <= n; i++)
    {
        if (grad[i] == 0)
        {
            cout << ' ' << i;
            exista = true;
        }
    }
    if (!exista)
    {
        cout << " niciunul";
    }
    cout << '\n';

    long long maxim = n * (n - 1) / 2;
    cout << "Complet: " << (m == maxim ? "DA" : "NU") << '\n';
    cout << "Muchii lipsa: " << maxim - m << '\n';
    return 0;
}

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