Problemă de grafuri clasa a XI-a, matematică-informatică, informatică ne-intensiv

Enunț

Se consideră un graf neorientat cu n vârfuri și m muchii, al cărei matrice de adiacență este citită de la tastatură. Fișierul „graf.txt” conține mai multe secvențe de vârfuri, aflate una sub alta, vârfurile fiecărei secvențe fiind scrise pe câte un rând și separate prin spații (nu se cunoaște câte astfel de secvențe există în fișier). Scrieți un program care afișează pe ecran acele secvențe de vârfuri din fișierul de intrare ce constituie lanțuri în graful dat, precizând pentru fiecare lanț dacă este elementar sau ne-elementar, apoi determină lanțul (lanțurile) de lungime maximă (reamintim că lungimea unui lanț este dată de numărul vârfurilor componente.

Exemplu

graf.txt:
1 2 6
8 7 6 1
3 4 5 3 2 8
5 3 2 7
1 2 8

fisier.in (în enunț, citit de la tastatură):
8 9
1 1 0 0 0 1 0 1
1 1 1 0 0 0 0 1
0 1 1 1 1 0 0 0
0 0 1 1 1 0 0 0
0 0 1 1 1 0 0 0
1 0 0 0 0 1 1 0
0 0 0 0 0 1 1 1
1 1 0 0 0 0 1 1

Se afișează în consolă:
1.
NU ESTE LANT
2.
ESTE LANT
ESTE ELEMENTAR
3.
ESTE LANT
NU ESTE ELEMENTAR
4.
NU ESTE LANT
5.
ESTE LANT
ESTE ELEMENTAR
Lanturile de lungime maxima 5 sunt in lista de lanturi:
 – al 2-lea

Codul sursă

#include
#include
#include
#include
using namespace std;

bool este_lant(int N, int M, vector<vector> &A,
    char line[], int l)
{
    string str = line;
    istringstream s(str);

    vector lant(0);
    int x;
    while (s >> x)
    {
        lant.push_back(x);
    }

    for (int i = 0; i < lant.size() – 1; ++i)
    {
        if (A[lant[i]][lant[i + 1]] == 0)
        {
            return false;
        }
    }
    return true;
}

bool este_elementar(int N, int M, vector<vector> &A,
    char line[], int l)
{
    string str = line;
    istringstream s(str);

    vector lant(0);
    int x;
    while (s >> x)
    {
        lant.push_back(x);
    }

    for (int i = 0; i < lant.size(); ++i)
    {
        for (int j = i + 1; j < lant.size(); ++j)
        {
            if (lant[i] == lant[j])
            {
                return false;
            }
        }
    }
    return true;
}

int main()
{
    int N, M;

    // primul fisier de intrare:
    ifstream in(„fisier.in”);
    in >> N >> M;
    vector<vector> A(N + 1, vector(N + 1));
    for (int i = 1; i <= N; ++i)
    {
        for (int j = 1; j <= N; ++j)
        {
            in >> A[i][j];
        }
    }
    in.close();


    // al doilea fisier de intrare:
    ifstream in2(„graf.txt”);

    // valorile de pe acelasi indice din vectorii
    // urmatori sunt asociate:
    vector lungimi_lanturi(0);
    vector id_lanturi(0);

    int id = 1;

    // va retine randul curent:
    char line[100];

    int l;
    do
    {
        // se citeste un rand intreg:
        in2.getline(line, 100);
        l = strlen(line);

        // randul este gol:
        if (l == 0) continue;

        // determina daca sirul de varfuri din randul curent
        // este un lant:
        bool e_lant = este_lant(N, M, A, line, l);

        // id este indicele (incepand de la 1) al randului curent:
        cout << (id++) << ". " << endl;

        // afiseaza daca este lant sau nu:
        cout << (e_lant ? "ESTE LANT" : "NU ESTE LANT") << endl;

        // daca e lant, se efectueaza verificari suplimentare:
        if (e_lant)
        {
            bool e_elementar = este_elementar(N, M, A, line, l);

            cout << (e_elementar ? "ESTE ELEMENTAR" : "NU ESTE ELEMENTAR") << endl;

            // se numara spatiile din rand pt. a afla lungimea
            // lantului:
            int spatii = 0;
            for (int i = 0; i < l; ++i)
            {
                if (line[i] == ‘ ‘)
                {
                    ++spatii;
                }
            }

            id_lanturi.push_back(id – 2);
            lungimi_lanturi.push_back(spatii);
        }
    } while (l > 0);
    
    in2.close();

    // se cauta lanturile de lungime maxima:
    int maxl = -1;
    for (int i = 0; i < id_lanturi.size(); ++i)
    {
        int lungime_lant = lungimi_lanturi[i];
        if (lungime_lant > maxl)
        {
            maxl = lungime_lant;
        }
    }

    cout << "Lanturile de lungime maxima " << maxl <<
        ” sunt in lista de lanturi:” << endl;
    for (int i = 0; i < id_lanturi.size(); ++i)
    {
        int lungime_lant = lungimi_lanturi[i];
        if (lungime_lant == maxl)
        {
            cout << " – al " << (i + 1) <<
                „-lea” << endl;
        }
    }

    return 0;
}

Lasă un răspuns

Completează mai jos detaliile tale sau dă clic pe un icon pentru a te autentifica:

Logo WordPress.com

Comentezi folosind contul tău WordPress.com. Dezautentificare /  Schimbă )

Fotografie Google

Comentezi folosind contul tău Google. Dezautentificare /  Schimbă )

Poză Twitter

Comentezi folosind contul tău Twitter. Dezautentificare /  Schimbă )

Fotografie Facebook

Comentezi folosind contul tău Facebook. Dezautentificare /  Schimbă )

Conectare la %s

%d blogeri au apreciat: