4112 - Falkland

Cerința

Pe teritoriul insulelelor FalkLand exista n britanici notati de la 1 la n si m argentinieni notati de la 1 la m.

Aceștia sunt în pragul războiului din pricina neînțelegerilor teritoriale. Pentru a restabili pacea prim-ministrul Marii Britanii Margaret Thatcher a venit cu o idee ingenioasă, care presupune renunțarea la acest teritoriu atât din partea Argentinei cât și a Marii Britanii, insulele Falkland urmând să devină un teritoriu autonom.

Deoarece în cazul unui război ambele părți au de pierdut, Leopoldo Galtieri(președintele Argentinei) a acceptat propunerea. Pentru a-și îndeplini planul, aceștia trebuie să detensioneze relațiile dintre argentinieni și britanici în scopul de a crea un teritoriu autonom prosper.

Fiecare britanic are diferite cunoștințe de naționalitate argentiniană pe insula. Deoarece aceștia se cunosc între ei, nu sunt dușmani de moarte, dar nici prieteni.

Se știe că fiecare britanic poate lega o singură relație de prietenie cu una dintre cunoștințele sale argentiniene și vice-versa. Pentru a detensiona relațiile, cele două naționalități sunt obligate să se cunoască și să lege cât mai multe relații de prietenie.

Având în vedere faptul că fiecare britanic poate lega o singură relație de prietenie cu un argentinian, iar relațiile de prietenie se știu deoarece acestea sunt evidente, Margaret Thatcher va solicită ajutorul în aflarea numărului maxim de relații noi de prietenie care se vor lega pe insula .

Date de intrare

Fișierul de intrare falklandIN.txt conține pe prima linie numerele n, m și k, reprezentând numărul de britanici, argentinieni și de relații de prietenie ce pot fi legate.

Pe următoarele k linii se află k perechii de numere x y cu semnificația : britanicul x poate lega o relație de prietenie cu argentinianul y.

Date de ieșire

Fișierul de ieșire falklandOUT.txt va conține pe prima linie numărul r, reprezentând numărul maxim de relații de prietenie ce pot fi legate pe insula .

Restricții și precizări

• 1 ≤ n, m ≤ 50.000
• 1 ≤ k ≤ 150.000
• 1 ≤ x ≤ n
• 1 ≤ y ≤ m

Exemplul 1:

falklandIN.txt

3 3 5
1 1
1 2
2 2
2 3
3 3

falklandOUT.txt

3

Exemplul 2:

falklandIN.txt

100000 100000 100000
1 1
1 2
2 2
2 3
3 3

falklandOUT.txt

Datele nu corespund restrictiilor impuse

Rezolvare

from collections import defaultdict

def verifica_restrictiile(n, m, k):
    if not (1 <= n <= 50000 and 1 <= m <= 50000 and 1 <= k <= 150000):
        with open("falklandOUT.txt", "w") as f:
            f.write("Datele nu corespund restrictiilor impuse")
        exit()

def numar_maxim_prieteni(n, m, k, prietenii):
    graf = defaultdict(list)

    for prietenie in prietenii:
        x, y = prietenie
        graf[x].append(y)

    def dfs(britanic, vizitat, potrivire):
        for argentinian in graf[britanic]:
            if not vizitat[argentinian]:
                vizitat[argentinian] = True

                if potrivire[argentinian] == -1 or dfs(potrivire[argentinian], vizitat, potrivire):
                    potrivire[argentinian] = britanic
                    return True

        return False

    def prietenii_maximi():
        potrivire = [-1] * (m + 1)
        rezultat = 0

        for i in range(1, n + 1):
            vizitat = [False] * (m + 1)
            if dfs(i, vizitat, potrivire):
                rezultat += 1

        return rezultat

    prieteni_maximi = prietenii_maximi()
    return prieteni_maximi

# Citirea datelor de intrare
with open("falklandIN.txt", "r") as f:
    n, m, k = map(int, f.readline().split())
    verifica_restrictiile(n, m, k)
    prietenii = [tuple(map(int, f.readline().split())) for _ in range(k)]

# Calcularea rezultatului
rezultat = numar_maxim_prieteni(n, m, k, prietenii)

# Scrierea rezultatului în fișierul de ieșire
with open("falklandOUT.txt", "w") as f:
    f.write(str(rezultat))