3603 - Quantum

Computerele cuantice ultramoderne funcționează pe baza arhitecturii interne a hiperprocesoarelor hadronice–dispozitive ce prelucrează optim datele prin intermediul interacțiunilor dintre particulele elementare ale fizicii cuantice, în cazul nostru quarkuri și gluoni.

Un astfel de procesor este conceput pe baza unei configurații extrem de stabile alcătuite din n quarkuri plasate într-un câmp de influență cuantic, a cărui integritate este conservată prin intermediul forței nucleare puternice.

Interacțiunea dintre quarkuri în cadrul hadronilor este asigurată de m gluoni – particule elementare ce propagă bidirecțional informația analizată în cadrul hiperprocesorului, creând așa-zise nuclee de divergență în structura câmpului de influență care permit prelucrarea eficientă a datelor stocate în qbiți. Aceste nuclee se definesc ca serii de quarkuri interconectate prin lanțuri ciclice de gluoni care, plasate într-un plan imaginar, nu prezintă puncte de convergență cu alte legături cuantice.

Cerința

Se cere testarea existenței unei încorporări în câmpul cuantic a configurației de hadroni ce compun hiperprocesorul, iar în caz afirmativ se va determina inclusiv o posibilă serie de nuclee de divergență.

Date de intrare

Pe prima linie a fișierului de intrare quantumin.txt se află valorile n – numărul de quarkuri – și m -numărul de gluoni -, iar pe următoarele m linii se află dispuse perechi de valori u, v ce definesc legăturile bidirecționale dintre quarkuri în hadroni.

Date de ieșire

Pe prima linie din fișierul de ieșire quantumout.txt se va afișa mesajul "SUCCESSFULLY EMBEDDING" în cazul existenței unei încorporări valide, iar apoi pe următoarea linie valoarea k – numărul de nuclee. Pe următoarele k linii se vor afișa nucleele astfel: numărul de quarkuri din nucleu și particulele elementare ce intră în componența acestuia. În cazul inexistenței unei astfel de încorporări se va afișa exclusiv mesajul "UNSUCCESSFULLY EMBEDDING".

Restricții și precizări

• 1 <= n <= 200, 1 <= m <= 20000, 1 <= u, v <= n;
• Se garantează pentru fiecare test că graful quarkurilor este conex.
• Un nucleu de divergență este un ciclu elementar.
• Se consideră nucleu de divergență inclusiv zona infinită ce înconjoară hadronii.

Exemplu 1

quantumin.txt

4 6

1 2

2 3

3 1

1 4

2 4

3 4

quantumout.txt

SUCCESSFULLY EMBEDDING

4

3 1 2 3

3 1 4 2

3 4 3 1

3 4 3 2

Exemplu 2

quantumin.txt

5 7

1 2

2 3

3 4

4 1

1 5

2 5

3 5

quantumout.txt

UNSUCCESSFULLY EMBEDDING

Rezolvare

#3603 - Quantum
def is_embedding_possible(n, m, edges):
    if not (1 <= n <= 200 and 1 <= m <= 20000):
        return "Fals"

    graph = {i: [] for i in range(1, n + 1)}

    for u, v in edges:
        if not (1 <= u <= n and 1 <= v <= n):
            return "Fals"
        graph[u].append(v)
        graph[v].append(u)

    def dfs(node, visited, current_nucleus):
        visited[node] = True
        current_nucleus.append(node)

        for neighbor in graph[node]:
            if not visited[neighbor]:
                dfs(neighbor, visited, current_nucleus)

    visited = {i: False for i in range(1, n + 1)}
    nuclei = []

    for node in range(1, n + 1):
        if not visited[node]:
            current_nucleus = []
            dfs(node, visited, current_nucleus)
            nuclei.append(current_nucleus)

    if len(nuclei) == 0:
        return "Fals"

    return "SUCCESSFULLY EMBEDDING\n{}\n{}".format(len(nuclei), "\n".join(" ".join(map(str, nucleus)) for nucleus in nuclei))

def main():
    try:
        with open('quantumin.txt', 'r') as input_file:
            n, m = map(int, input_file.readline().split())
            edges = [tuple(map(int, input_file.readline().split())) for _ in range(m)]

        result = is_embedding_possible(n, m, edges)

        with open('quantumout.txt', 'w') as output_file:
            output_file.write(result)
    except Exception as e:
        print("Fals")

if __name__ == "__main__":
    main()