fbpx

Problema #473 – BipartitComplet – Rezolvari PBInfo

de Mihai-Alexandru

Cerinţa

Se consideră două mulţimi nevide A şi B, cu proprietatea că formează o partiție a mulțimii {1,2,...,n}. Să se construiască un graf bipartit complet cu n vârfuri, bipartit peste partiţia formată din mulțimile A și B.

Date de intrare

Fişierul de intrare bipartitcomplet.in conţine pe prima linie numărul n. Urmează un număr k, apoi k numere naturale distincte cuprinse între 1 și n, reprezentând vârfurile din A. Mulțimea B conține toate numerele naturale cuprinse între 1 și n care nu sunt în A.

Date de ieşire

Fişierul de ieşire bipartitcomplet.out va conţine matricea de adiacență a grafului construit, câte o linie a matricei pe o linie a fișierului, elementele de pe o linie fiind separate prin exact un spațiu.

Restricţii şi precizări

  • 1 < k < n ≤ 100

Exemplu

bipartitcomplet.in

7
3 
4 6 3

bipartitcomplet.out

0 0 1 1 0 1 0 
0 0 1 1 0 1 0 
1 1 0 0 1 0 1 
1 1 0 0 1 0 1 
0 0 1 1 0 1 0 
1 1 0 0 1 0 1 
0 0 1 1 0 1 0 
#include <bits/stdc++.h>
using namespace std;
ifstream fin ("bipartitcomplet.in");
ofstream fout ("bipartitcomplet.out");
int a[101][101], n, m , x, y, k , v[2500];
int main()
{
    fin >> n;
    fin >> k;
    for(int i = 1 ; i <= k ; ++i)
        fin >> v[i];
    for(int i = 1 ; i <= n ; i++)
    {
        for(int j = 1 ; j <= n ; ++j)
        {
            for(int p = 1 ; p <= k ; ++p)
            {
                if(i == v[p])
                {
                    if(a[i][j] == 0) a[i][j] = 1;
                }
            }
        }
    }
    for(int j = 1 ; j <= n ; j++)
    {
        for(int i = 1 ; i <= n ; ++i)
        {
            for(int p = 1 ; p <= k ; ++p)
            {
                if(j == v[p])
                {
                    if(a[i][j] == 1) a[i][j] = 0;
                    else a[i][j] = 1;
                }
            }
        }
    }
    for(int i = 1 ; i <= n ; ++i)
    {
        for(int j= 1 ; j <= n ; ++j)
            fout << a[i][j] << " ";
        fout << endl;
    }
    return 0;
}
Comentarii

S-ar putea sa iti placa