1462 - Gasti

Enunț

În orașul Nicăieri există N băieți răi. Se știe că între ei există M relații de prietenie. De-a lungul timpului, aceste prietenii au dus la apariția unor “găști”. Dacă doi băieți nu sunt prieteni dar au cel puțin un prieten comun spunem că “se cunosc”. Dacă doi băieți au cel puțin o cunoștință comună, atunci și ei se cunosc. O gașcă este un grup de băieți cu proprietatea că oricare ar fi doi băieți x și y din grup, aceștia “se cunosc”.

Cerința

Arpsod, știe exact cine este prieten cu cine și, fiind singurul băiat bun din oraș, și-a pus următoarele întrebări:

1. Câte găști există în oraș.

2. Dacă ar mai exista O SINGURĂ relație de prietenie pe lângă cele date, în câte moduri ar putea apărea aceasta, astfel încât să se obțină o gașcă cu număr maxim de membri. Pentru că numărul de moduri poate fi foarte mare, Arpsod se mulțumește cu restul împărțirii rezultatului la 666013.

Pentru că e prea ocupat să se baricadeze în casă de frica băieților răi, Arpsod vă roagă pe voi să aflați cele două răspunsuri

Date de intrare

Pe prima linie a fișierului gastiIN.txt se vor afla două numere naturale N și M reprezentând numărul de băieți răi, respectiv numărul de relații de prietenie. Următoarele M linii vor conține câte două numere naturale x și y cu semnificația că există o relație de prietenie între băiatul x și băiatul y.

Date de ieșire

Pe singura linie a fișierului gastiOUT.txt se vor afișa două numere separate prin spațiu, primul reprezentând răspunsul pentru prima cerința iar cel de-al doilea pentru a doua cerință.În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Nu corespunde restricțiilor impuse".

Restricții și precizări

• 1 ≤ N ≤ 100.000
• 0 ≤ M ≤ 300.000
• Dacă x este prieten cu y atunci și y este prieten cu x
• Toate relațiile de prietenie sunt unice
• La numărarea modurilor de adaugare a unei prietenii, prietenia x y si prietenia y x coincid
• Se garanteaza ca pentru 30% din teste 1 ≤ N ≤ 1000
• Pentru rezolvarea corectă a primei cerințe se acordă 40% din punctajul pe testul respectiv iar pentru rezolvarea corectă a celei de-a doua cerințe se acordă 60% din punctajul pe testul respectiv
• Fișierul de ieșire TREBUIE să conțină DOUĂ valori chiar dacă doriți să rezolvați o singură cerință din cele două
• Arpsod înțelege cel mai bine hit-ul lui Bob Marley: “Bad Boys”

Exemplul 1:

gastiIN.txt

5 3
1 2
2 3
3 1

gastiOUT.txt

3 6

Explicație

Există 3 găști în oraș, formate:

Gașca 1: 1, 2, 3

Gașca 2: 4

Gașca 3: 5

Sunt 6 moduri de a face o relație de prietenie astfel încât gașca obținută să aibă număr maxim de membri

4 cu 1, 4 cu 2, 4 cu 3, 5 cu 1, 5 cu 2, 5 cu 3

Exemplul 2:

gastiIN.txt

1000001 23
1 2
2 3
3 1

gastiOUT.txt

Datele nu corespund restrictiilor impuse

Rezolvare

<syntaxhighlight lang="python3" line="1"> def DFS(node, gasca):

   global cnt
   cnt += 1
   Gasca[node] = gasca

   for neighbor in G[node]:
       if Gasca[neighbor] == 0:
           DFS(neighbor, gasca)

def verifica_restrictii(N, M, G):

   if not (1 <= N <= 100000 and 0 <= M <= 300000):
       return "Datele nu corespund restrictiilor impuse"

   for i in range(1, N + 1):
       if not (0 <= len(G[i]) <= 100000):
           return "Datele nu corespund restrictiilor impuse"

   return None

Nmax = 100002 Mod = 666013

G = [[] for _ in range(Nmax)] Gasca = [0] * Nmax Members = [0] * Nmax Cate = [0] * Nmax

cnt = 0

with open("gastiIN.txt", "r") as fin:

   N, M = map(int, fin.readline().split())

   restrictii_msg = verifica_restrictii(N, M, G)
   if restrictii_msg is not None:
       with open("gastiOUT.txt", "w") as fout:
           fout.write(restrictii_msg)
       exit()

   for _ in range(M):
       x, y = map(int, fin.readline().split())
       if y not in G[x]:
           G[x].append(y)
       if x not in G[y]:
           G[y].append(x)

gasti = 0 max1, max2 = -1, -1

for i in range(1, N + 1):

   if Gasca[i] == 0:
       cnt = 0
       gasti += 1
       DFS(i, gasti)
       Members[gasti] = cnt
       Cate[Members[gasti]] += 1

       if Members[gasti] > max1:
           max2 = max1
           max1 = Members[gasti]
       elif Members[gasti] > max2:
           max2 = Members[gasti]

if max1 != max2:

   x = (Cate[max1] * max1) % Mod
   y = (Cate[max2] * max2) % Mod

else:

   x = (max1 * max1) % Mod
   y = (Cate[max1] * (Cate[max1] - 1) // 2) % Mod

rez = (x * y) % Mod

with open("gastiOUT.txt", "w") as fout:

   fout.write(f"{gasti} {rez}")

</syntaxhighlight>