adj-mat

#include <iostream>
using namespace std;


const int N = 128;
int mat[N][N]; // matricea de adiacenta - folosita in mai multe probleme
int nr; // numarul de linii si coloane


void fill_mat()
{
    /// Functie pentru completarea matricei de adiacenta.
    cout << "Dimensiune: ";
    cin >> nr;
    for (int i = 1; i <= nr; ++i) {
        for (int j = 1; j <= nr; ++j) {
            cout << i << "-" << j << ": ";
            cin >> mat[i][j];
        }
    }
}


bool f8()
{
    // mai folosim functia asta si in alta problema
    // de aceea returneaza ceva :)
    // graf neorientat -> mat[a][b] == mat[b][a]
    // verificam deasupra diagonalei principale (nu e nevoie neaparat si sub)
    for (int i = 1; i <= nr; ++i) {
        for (int j = i + 1; j <= nr; ++j)
        if (mat[i][j] != mat[j][i]) {
            // avem muchie de la un nod la altul dar nu si invers
            // deci graful este orientat
            cout << "Nu" << endl;
            return 0;
        }
    }
    cout << "Da" << endl;
    return 1;
}


void f11()
{
    // aici sigur trebuie sa citim si matricea de adiacenta
    // sa stim de ce muchii dispunem
    int vec1[N], vec2[N];
    int len1, len2;
    cout << "Dimensiune v1: ";
    cin >> len1;
    cout << "Dimensiune v2: ";
    cin >> len2;
    cout << "Elemente v1: ";
    for (int i = 0; i < len1; ++i) cin >> vec1[i];
    cout << "Elemente v2: ";
    for (int i = 0; i < len2; ++i) cin >> vec2[i];
    /* graf bipartit complet: de la fiecare nod sa existe muchie la fiecare alt nod
       si pentru fiecare muchie un nod sa se gaseasca in multimea v1 si celalalt in v2
       mai exact de la fiecare nod din v1 sa existe o muchie la toate celelalte noduri din v2
       si sa nu existe muchii de la vreun nod din v1 la un nod tot in v1
    */
    for (int i = 0; i < len1; ++i) {
        int nod = vec1[i];
        // verificam sa nu existe muchie in interior
        for (int j = 0; j < len1; ++j) {
            if (mat[nod][vec1[j]] || mat[vec1[j]][nod]) {
                // exista
                cout << "Nu" << endl;
                return;
            }
        }
        // totul ok pentru nodul i mai ramane sa verificam
        // existenta muchiilor de la el la toate celelalte din v2
        for (int j = 0; j < len2; ++j) {
            // doar in cazul bun (atunci cand exista drum si inainte
            // si inapoi de la nod din v1 la nod din v2) expresia va fi 0/falsa
            if (!(mat[nod][vec2[j]] && mat[vec2[j]][nod])) {
                cout << "Nu" << endl;
                return;
            }
        }
    }
    cout << "Da" << endl;
}


void dfs(int nod, bool vazut[])
{
    // marcam ca vizitat nodul curent si apoi vizitam toti ceilalti vecini
    // asta daca nu a fost deja vizitat acest nod
    if (vazut[nod]) return; // iesim
    // nevizitat, vizitam
    vazut[nod] = 1;
    for (int i = 1; i <= nr; ++i) {
        if (mat[nod][i]) dfs(i, vazut);
    }
}


bool f21()
{
    // si pe asta o mai folosim
    // un graf neorientat este conex daca din oricare nod se poate ajunge in oricare nod
    // este de ajuns sa facem o parcurgere dintr-un nod la toti ceilalti vecini
    // si daca raman noduri nevizitate inseamna ca nu s-a putut ajunge la ele
    // deci graful nu-i conex
    bool vazut[N]; // 0-nevizitat 1-vizitat
    for (int i = 0; i < N; ++i) vazut[i] = 0;
    // vam parcurge graful in adancime
    dfs(1, vazut); // mereu exista un prim nod
    // acum daca a ramas vreun nod nevizitat clar ca nu e conex
    for (int i = 1; i <= nr; ++i) if (!vazut[i]) {
        cout << "Nu" << endl;
        return 0;
    }
    cout << "Da" << endl;
    return 1;
}


bool check(int from, int nod, bool vazut[])
{
    // functia returneaza 1 daca a gasit ciclu
    // si 0 in caz contrar (atunci cand e ok pentru un arbore)
    if (vazut[nod]) return 1;
    for (int i = 1; i <= nr; ++i) {
        if (mat[nod][i] && i != from) {
            // daca exista drum de la nod la i si
            // nodul in care ne vom deplasa difera de nodul din care am venit
            // atunci vizitam, asta pentru ca sa nu ne pacalim singuri
            // ca ar fi ciclu fiindca nodul din care venim intotdeauna e vizitat
            return check(nod, i, vazut);
        }
    }
}


void f22()
{
    // arbore = graf neorientat conex aciclic
    if (!(f8() && f21())) {
        // nu este neorientat conex
        cout << "Nu" << endl;
        return;
    }
    // acum verificam sa nu aiba cicluri
    // procedam similar ca si la vizita (dfs) numai ca functia va avea alta conotatie
    // acum vom tine minte din ce nod am venit ca sa nu ne intoarcem in acesta
    // si in timpul parcurgerii vom verifica daca a mai fost vizitat deja un nod
    // daca a mai fost vizitat e clar ca s-a putut ajunge in el si din alta parte
    // o alta parte decat traseul curent deci avem un ciclu, circuit inchis
    // deci nu se mai numeste arbore
    bool vazut[N];
    for (int i = 0; i < N; ++i) vazut[i] = 0;
    if (check(0, 1, vazut)) {
        cout << "Nu" << endl;
        return;
    }
    cout << "Da" << endl;
}


int main()
{
    fill_mat();
    f8();
    f11();
    f21();
    f22();
    return 0;
}