Rus Marius: Pagină nouă: == 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...

2024-01-06T18:14:24Z

Pagină nouă: == Enunț == În orașul Nicăieri există <code>N</code> băieți răi. Se știe că între ei există <code>M</code> 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...

New page

== Enunț ==
În orașul Nicăieri există <code>N</code> băieți răi. Se știe că între ei există <code>M</code> 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 <code>x</code> și <code>y</code> 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 <code>666013</code>.

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 <code>gastiIN.txt</code> se vor afla două numere naturale <code>N</code> și <code>M</code> reprezentând numărul de băieți răi, respectiv numărul de relații de prietenie. Următoarele <code>M</code> linii vor conține câte două numere naturale <code>x</code> și <code>y</code> cu semnificația că există o relație de prietenie între băiatul <code>x</code> și băiatul <code>y</code>.

= Date de ieșire =
Pe singura linie a fișierului <code>gastiOUT.txt</code> 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 =

* <code>1 ≤ N ≤ 100.000</code>
* <code>0 ≤ M ≤ 300.000</code>
* Dacă <code>x</code> este prieten cu <code>y</code> atunci și <code>y</code> este prieten cu <code>x</code>
* Toate relațiile de prietenie sunt unice
* La numărarea modurilor de adaugare a unei prietenii, prietenia <code>x y</code> si prietenia <code>y x</code> coincid
* Se garanteaza ca pentru <code>30%</code> din teste <code>1 ≤ N ≤ 1000</code>
* Pentru rezolvarea corectă a primei cerințe se acordă <code>40%</code> din punctajul pe testul respectiv iar pentru rezolvarea corectă a celei de-a doua cerințe se acordă <code>60%</code> 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: =
<code>gastiIN.txt</code>
5 3
1 2
2 3
3 1
<code>gastiOUT.txt</code>
3 6

=== Explicație ===
Există <code>3</code> găști în oraș, formate:

Gașca <code>1</code>: <code>1</code>, <code>2</code>, <code>3</code>

Gașca <code>2</code>: <code>4</code>

Gașca <code>3</code>: <code>5</code>

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

<code>4</code> cu <code>1</code>, <code>4</code> cu <code>2</code>, <code>4</code> cu <code>3</code>, <code>5</code> cu <code>1</code>, <code>5</code> cu <code>2</code>, <code>5</code> cu <code>3</code>

== Exemplul 2: ==
<code>gastiIN.txt</code>
1000001 23
1 2
2 3
3 1
<code>gastiOUT.txt</code>
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>

1462 - Gasti - Revision history