1497 - Nunta

Enunț

La o nuntă sunt invitate n persoane, numerotate de la 1 la n. Se știe că o parte din ele se cunosc două câte două, fie că sunt rude, fie de la serviciu, fie sunt prieteni sau vecini. Astfel se vor forma un număr K minim de grupuri astfel încât în fiecare grup, fiecare persoană să aibă cel puţin un cunoscut. Pentru fiecare grup de cel puțin două persoane se stabileşte un lider – persoana cu numărul de ordine minim. Aceste grupuri vor fi numerotate de la 1 la K în ordinea crescătoare a numerelor de ordine ale liderilor. Ca sa se ivească cât mai puține situații stânjenitoare, organizatorul nunții ar dori să aranjeze o masă principală cu cel puţin n/2+1 invitaţi, la care să fie aşezate unul sau mai multe astfel de grupuri întregi numerotate cu valori consecutive.

Cerința

Fiind date n, numărul de persoane, m, numărul de perechi de invitaţi care se cunosc între ei și cele m perechi, să se determine numărul K minim de grupuri formate din cel puțin doi invitați astfel încât, în fiecare grup, fiecare persoană să aibă cel puţin un cunoscut, precum şi numărul variantelor distincte în care se poate organiza masa cu cel puţin n/2+1 invitaţi din grupurile formate.

Date de intrare

Fișierul de intrare nuntaIN.txt conține pe prima linie două numere naturale separate prin spațiu n și m, n reprezentând numărul de invitaţi, respectiv m numărul de perechi de invitaţi care se cunosc între ei. Pe fiecare din următoarele m linii se află câte două numere naturale x și y, 1≤x, y≤n, separate printr-un spațiu, cu semnificația că invitaţii x și y se cunosc între ei.

Date de ieșire

Fișierul de ieșire nuntaOUT.txt va conține pe prima linie un număr natural g reprezentând numărul minim de grupuri formate din cel puțin doi invitați astfel încât, în fiecare grup, fiecare persoană să aibă cel puţin un cunoscut. Pe cea de a doua linie va fi scris un număr natural v reprezentând numărul variantelor distincte în care se poate organiza masa cu cel puţin n/2+1 invitaţi din grupurile formate.În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Datele nu corespund restrictiilor impuse".

Restricții și precizări

• 0 < n <= 20000
• 0 < m <= 100000

Exemplul 1:

nuntaIN.txt

31 6
5 7
2 3
10 14
14 6
9 15
7 30

nuntaOUT.txt

4
0

Explicație

Grupurile formate din cel puțin doi invitați sunt : (2,3), (5,7,30), (6,10,14), (9,15), deci K=4. Ele nu sunt suficiente pentru a forma o masă cu cel puţin 16 invitaţi, deci sunt 0 variante de aranjare.

Exemplul 1:

nuntaIN.txt

20001 6
5 7
2 3
10 14
14 6
9 15
7 30

nuntaOUT.txt

Datele nu corespund restrictiilor impuse

Rezolvare

from collections import namedtuple

nMAX = 20000

class Component:
    def __init__(self):
        self.min = float('inf')
        self.cnt = 0

components = [Component() for _ in range(nMAX + 1)]
gf = [[] for _ in range(nMAX + 1)]
viz = [0] * (nMAX + 1)

def check_constraints(n, m):
    if not (0 < n <= 20000) or not (0 < m <= 100000):
        with open("nuntaOUT.txt", "w") as fout:
            fout.write("Datele nu corespund restrictiilor impuse")
        return False
    return True

def dfs(nod, fil):
    viz[nod] = fil
    for nex in gf[nod]:
        if not viz[nex]:
            dfs(nex, fil)

def main():
    global nMAX
    global gf
    global viz
    global components

    with open("nuntaIN.txt", "r") as fin:
        n, m = map(int, fin.readline().split())

        if not check_constraints(n, m):
            return

        with open("nuntaOUT.txt", "w") as fout:
            for _ in range(m):
                a, b = map(int, fin.readline().split())
                gf[a].append(b)
                gf[b].append(a)

            fil = 0
            for i in range(1, n + 1):
                if not viz[i]:
                    fil += 1
                    dfs(i, fil)

            for i in range(1, n + 1):
                components[i].min = float('inf')

            for i in range(1, n + 1):
                components[viz[i]].min = min(components[viz[i]].min, i)
                components[viz[i]].cnt += 1

            components = sorted(components[1:fil + 1], key=lambda x: (x.cnt == 1, x.min))

            while components[fil - 1].cnt == 1:
                fil -= 1

            fout.write(str(fil) + '\n')

            dr = 0
            s = 0
            ne = 0
            for st in range(1, fil + 1):
                while dr + 1 <= fil and s + components[dr].cnt < n // 2 + 1:
                    s += components[dr].cnt
                    dr += 1

                if s + components[dr].cnt < n // 2 + 1:
                    break

                ne += fil - dr
                s -= components[st - 1].cnt

            fout.write(str(ne))

if __name__ == "__main__":
    main()