Discussion

[alhasanmridha]

[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.