View source for 0466 - Gen Graf

= Cerinţa =
Se dă un număr natural <code>n</code>. Construiți toate grafurile neorientate cu <code>n</code> vârfuri.

= Date de intrare =
Fişierul de intrare <code>gengrafIN.txt</code> conţine pe prima linie numărul <code>n</code>.

= Date de ieşire =
Fişierul de ieşire <code>gengrafOUT.txt</code> va conţine pe prima linie numărul de grafuri generate <code>M</code>; urmează <code>M</code> matrice de adiacență ale acestor grafuri.

Fiecare matrice va fi afișată astfel: câte o linie a matricei pe o linie a fișierului, elementele de pe o linie fiind separate prin exact un spațiu. După fiecare matrice afișată se va găsi în fișier o linie goală.

= Restricţii şi precizări =

* <code>2 ≤ n ≤ 6</code>
* cele <code>M</code> matrice de adiacență construite pot fi afișate în orice ordine

== Exemplul 1 ==
gengrafIN.txt:

3

gengrafOUT.txt:

8

0 0 0

0 0 0

0 0 0

0 1 0

1 0 0

0 0 0

0 0 1

0 0 0

1 0 0

0 1 1

1 0 0

1 0 0

0 0 0

0 0 1

0 1 0

0 1 0

1 0 1

0 1 0

0 0 1

0 0 1

1 1 0

0 1 1

1 0 1

1 1 0

== Exemplul 2 ==
gengrafIN.txt:

7

Output:

Valoarea lui n nu respectă restricția 2 <= n <= 6.

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
def generate_graphs(n):
    graphs = []
    for i in range(2**(n*(n-1)//2)):
        graph_matrix = [[0]*n for _ in range(n)]
        idx = 0
        for j in range(n):
            for k in range(j+1, n):
                graph_matrix[j][k] = graph_matrix[k][j] = (i >> idx) & 1
                idx += 1
        graphs.append(graph_matrix)
    return graphs

def write_to_file(graphs, filename):
    with open(filename, 'w') as file:
        file.write(str(len(graphs)) + '\n')
        for graph in graphs:
            for row in graph:
                file.write(' '.join(map(str, row)) + '\n')
            file.write('\n')

def check_n_range(n):
    return 2 <= n <= 6

if __name__ == "__main__":
    with open('gengrafIN.txt', 'r') as input_file:
        n = int(input_file.readline().strip())

    if check_n_range(n):
        graphs = generate_graphs(n)
        write_to_file(graphs, 'gengrafOUT.txt')
    else:
        print("Valoarea lui n nu respectă restricția 2 <= n <= 6.")

</syntaxhighlight>