Discussion

[alhasanmridha]

Discussion

[Ankitdulani]

	int count_new=0;
	for(int i=0;i<n;i++){
		if(parent[i]==a){
			count_new++;
		}
	}
	count += 2*(count_new-1);

I was using this logic to count the red strand!
I'm not able to comprehend where it could go wrong.

[Ankitdulani]

#include<bits/stdc++.h>
using namespace std;

int getParent(vector&parent,int a){
if(parent[a]==a)
return a;
return getParent(parent,parent[a]);
}
int main(){
int t;
cin>>t;
for(int i=1;i<=t;i++){
int n,m;
cin>>n>>m;

	vector<int>parent(n,0);
	for(int i=0;i<n;i++)
		parent[i]=i;

	int count=0;

	while(m--){
		int a,b;
		cin>>a>>b;
		a--;b--;

		int pa= getParent(parent,a);
		int pb = getParent(parent,b);
		if(pa!=pb){
			count++;
			parent[pa]=pb;
		}
	}

	int count_new=0;
	for(int i=0;i<n;i++){
		if(parent[i]==i){
			count_new++;
		}
	}


	count += 2*(count_new-1);
	cout<<"Case #"<<i<<": "<<count<<endl;
}
return 0;

}

---

[alhasanmridha]

You need to use return parent[a]=getParent(parent,parent[a]); in getParent(vector<int>& parent,int a) to reduce the length of hierarchy. You can find more about path compression here.