Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<fstream>
- #define nmax 5000
- #define comanda 1
- using namespace std;
- struct nod
- {int elem,cheie;
- nod *st,*dr;};
- struct operatie{
- int x,y,tip;};
- int tata[nmax+1],h[nmax+1],rasp[nmax];
- int N,nrk,nrrasp;
- nod *v[nmax];
- operatie op[nmax+1];
- //Proceduri arbori
- void adauga(nod* &rad,int elem,int cheie)
- {
- if(rad==NULL)
- {
- rad=new nod;
- rad->elem=elem;
- rad->cheie=cheie;
- rad->st=rad->dr=NULL;
- }
- else
- {
- if(elem<rad->elem)
- adauga(rad->st,elem,cheie);
- else
- adauga(rad->dr,elem,cheie);
- }
- }
- int det_cheie(nod* rad,int elem)
- {
- while(rad!=NULL)
- {
- if(rad->elem==elem)
- return rad->cheie;
- if(elem<rad->elem)
- rad=rad->st;
- else
- rad=rad->dr;
- }
- return 0;
- }
- void eliberare(nod* &rad)
- {
- if(rad!=NULL)
- {
- if(rad->st)
- eliberare(rad->st);
- if(rad->dr)
- eliberare(rad->dr);
- delete rad;
- }
- }
- //Proceduri multimi
- int reprezentant(int elem);
- int reprezentant_cheie(int cheie);
- void unifica(int elem1,int elem2)
- {
- int x,y;
- x=reprezentant_cheie(det_cheie(v[elem1%nmax],elem1));
- y=reprezentant_cheie(det_cheie(v[elem2%nmax],elem2));
- if(h[x]>h[y])
- {
- tata[y]=x;
- }
- else
- {
- tata[x]=y;
- if(h[x]==h[y])
- h[y]++;
- }
- }
- int reprezentant(int elem)
- {
- int x,y,t,r;
- x=det_cheie(v[elem%nmax],elem);
- r=x;
- while(tata[r])
- r=tata[r];
- y=x;
- while(y!=r)
- {
- t=tata[y];
- tata[y]=r;
- y=t;
- }
- return r;
- }
- int reprezentant_cheie(int cheie)
- {
- int x,y,t,r;
- x=cheie;
- r=x;
- while(tata[r])
- r=tata[r];
- y=x;
- while(y!=r)
- {
- t=tata[y];
- tata[y]=r;
- y=t;
- }
- return r;
- }
- void init_arbori()
- {
- int i,x,y;
- for(i=1;i<=N;i++)
- {
- if((det_cheie(v[op[i].x%nmax],op[i].x))== 0)
- {nrk++;
- adauga(v[op[i].x%nmax],op[i].x,nrk);
- }
- if((det_cheie(v[op[i].y%nmax],op[i].y))==0)
- {
- nrk++;
- adauga(v[op[i].y%nmax],op[i].y,nrk);
- }
- }
- }
- void rezolva()
- {
- int i,r1,r2;
- init_arbori();
- for(i=1;i<=N;i++)
- {
- if(op[i].tip==comanda)
- unifica(op[i].x,op[i].y);
- else
- {
- nrrasp++;
- r1=reprezentant(op[i].x);
- r2=reprezentant(op[i].y);
- if(r1==r2)
- rasp[nrrasp]=1;
- else
- rasp[nrrasp]=0;
- }
- }
- for(i=0;i<N;i++)
- eliberare(v[i]);
- }
- void citeste()
- {
- int i;
- ifstream f("entries.in");
- f>>N;
- for(i=1;i<=N;i++)
- f>>op[i].x>>op[i].y>>op[i].tip;
- f.close();
- }
- void scrie()
- {
- int i;
- ofstream g("entries.out");
- for(i=1;i<=nrrasp;i++)
- g<<rasp[i]<<'\n';
- g.close();
- }
- int main()
- {
- citeste();
- rezolva();
- scrie();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement