Reference no: EM13803429

What is the output of the given program:

#include <iostream>

#include <algorithm>

using namespace std;

int cnt=0;
int Even=0;
int sz[1000005];
int id[1000005];
void UF(int N)
{
  cnt = N;
  for(int i=0; i<N; i++){
  id[i] = i;
  sz[i] = 1;
}
}

int find(int p) {
int root = p;
while (root != id[root])
root = id[root];
while (p != root) {
int newp = id[p];
id[p] = root;
p = newp;
}
return root;
}
void merge(int x, int y) {
int i = find(x);
int j = find(y);
if (i == j) return;

if (sz[i] < sz[j]){
id[i] = j;
if(sz[i]%2==0)
Even--;
int prev=sz[j];
sz[j] += sz[i];
cout<<"**"<<sz[i]<<" "<<prev<<" "<<sz[j]<<endl;
if(sz[j]%2==0 && prev%2!=0)
Even++;
if(sz[j]%2!=0 && prev%2==0)
Even--;

} else {
id[j] = i;
if(sz[j]%2==0)
Even--;
int prev=sz[i];
sz[i] += sz[j];
cout<<"&&"<<sz[i]<<" "<<prev<<" "<<sz[j]<<endl;
if(sz[i]%2==0 && prev%2!=0)
Even++;
if(sz[i]%2!=0 && prev%2==0)
Even--;
}
cnt--;
}

bool connected(int x, int y){
return find(x) == find(y);
}

int count(){
return cnt;
}
int main()
{
int friends,Conn,A,B;
cin>>Conn;
UF(100005);
char C;
for(int i=0;i<Conn;i++){
cin>>C>>A>>B;
if(C=='C')
merge(A,B);
else
cout<<Even;
cout<<endl;
}
return 0;
}