Se consideră un graf care inițial este format din P noduri izolate, etichetate de la 1 la P. Se mai consideră N intrări, unde intrare poate însemna:

comandă – o comandă are forma I + J, cu semnificația că în graf se adaugă muchia care unește nodurile I și J (dacă I și J erau deja unite în acel moment, nu se întreprinde nici o acțiune);
întrebare – o întrebare este de forma I ? J, adică se întreabă dacă în acel moment I și J sunt în aceeași componentă conexă.

Se pleacă deci de la un graf inițial format din noduri izolate, care pe parcurs se “unifică”. Tot pe parcurs sunteți întrebat dacă anumite perechi de noduri sunt sau nu în aceeași componentă conexă.

Cerința

Scrieți un program care să răspundă la întrebările din fișierul de intrare.

Date de intrare

Din fișierul entries.in veți citi de pe prima linie numărul N de intrări. Pe următoarele N linii se găsesc intrările, câte una pe linie. O intrare este codificată prin trei numere separate prin câte un blanc. Primele două numere reprezintă nodurile I și J (numere întregi, cuprinse între 1 și P), iar al treilea este 1 dacă intrarea este o comandă, respectiv 2 dacă intrarea este o întrebare.

Date de ieșire

Fișierul de ieșire entries.out va conține răspunsurile la întrebări, câte un răspuns pe o linie, în ordinea din fișierul de intrare. Răspunsul va fi numărul 1 dacă nodurile despre care ați fost întrebat sunt în acel moment în aceeași componentă conexă, respectiv numărul 0 în caz contrar.

Restricții și precizări

1 ≤ N ≤ 5 000
1 ≤ P ≤ 10.000.000

Exemplu

entries.in

entries.out

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema entries:

#include<bits/stdc++.h>

using namespace std;

ifstream fin ("entries.in");
ofstream fout ("entries.out");

map<int, int> M;
map<int, int> :: iterator it;

int t[10005], n;

int Find(int x)
{
  int z,y;
  y = x;
  while (t[x]!=0)
     x = t[x];

  while (t[y]!=0)
  {
     z = t[y];
     t[y] = x;
     y = z;
  }

  return x;
}

inline void Union(int x, int y)
{
    t[y] = x;
}

int main ()
{
    int T, x, y, op, k;
    fin >> T;
    while (T--)
    {
        fin >> x >> y >> op;
        k = 0;
        it = M.find(x);
        if (it == M.end()) {k = 1; n++; M[x] = n;}
        it = M.find(y);
        if (it == M.end()) {k = 1; n++; M[y] = n;}

        x = M[x];
        y = M[y];
        x = Find(x);
        y = Find(y);
        if (op == 1)
        {
            if (x != y) Union(x, y);
        }
        else
        {
            if (k == 1) fout << "0\n";
            else if (x == y) fout << "1\n";
            else fout << "0\n";
        }

    }
    fin.close();
    fout.close();
    return 0;
}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email .

Rezolvarea problemei #3235 entries

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #3235 entries de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!

Rezolvare completă PbInfo #3235 entries