👤
a fost răspuns

Buna seara, am nevoie de ajutor la problema exam de pe campion in c sau c++.

La facultatea de informatica, datorita numarului mare de cursuri optionale oferite studentilor, planificarea examenelor este dificila.
Cursurile sunt numerotate de la 1 la n si fiecare student trebuie sa îsi aleaga exact doua cursuri optionale.
Toate examenele trebuie sa fie planificate dimineata, de la 9.00 la 12.00.
Evident, un student nu poate sa participe la doua examene în acelasi timp.
Planificarea examenelor trebuie sa fie facuta astfel încât toti studentii sa poata sustine examenele.

Cerinta

Scrieti un program care sa determine numarul minim de zile necesare pentru ca toti studentii sa poata sustine examenele la cursurile optionale.

Date de intrare

Fisierul de intrare exam.in contine pe prima linie doua numere naturale separate prin spatiu n si m, unde n reprezinta numarul de cursuri optionale, iar m reprezinta numarul de studenti. Pe urmatoarele m linii sunt scrise optiunile celor m studenti. Mai exact, pe linia i+1 sunt scrise doua numere distincte cuprinse între 1 si n, reprezentând cursurile pentru care a optat studentul i.

Date de iesire

Fisierul de iesire exam.out va contine o singura linie pe care va fi scris determine numarul minim de zile necesare pentru ca toti studentii sa poata sustine examenele la cursurile optionale.

Restrictii si precizari

2 <= n <= 1000
1 <= m <= 5000

Răspuns :

Express
#include <bits/stdc++.h>
using namespace std;
int n, m, i, j, x, y, sol;
bool a[1002][5002], v[1005];
int main()
{
    ifstream f("exam.in");
    ofstream g("exam.out");
    f >> n >> m;
    for(i = 1; i <= m; i++)
       {
         f >> x >> y;
         a[x][y] = a[y][x] = true;
       }
    for(i = 1; i <= n; i++)
    {
        if(!v[i])
        {
            v[i] = true;
            for(j = i + 1; j <= n; j ++)
            if(!a[i][j])
                v[j] = true;
            sol ++;
        }
    }
    g << sol;
    return 0;
}

Alte intrebari