#include<iostream>
#include<vector>
#define min(x,y)(x>y?y:x)
#define max(x,y)(x>y?x:y)
using namespace std;
int main()
{
int t,n,m,x,y;
cin>>t;
while(t--)
{int check=0,count=0;
vector<int>b(100004),a(100004);    // a is for storing parent while b for storing no of connected node to parent
	cin>>n>>m;
	count=n;                                //count is variable for storing no of total nodes.
	if(m==0)cout<<n<<endl;
	else
	{
	for(int k=0;k<m;k++)
	{
	cin>>x>>y;
	if(a[x+1]==0&&a[y+1]==0)
	{
		a[x+1]=min(x+1,y+1);a[y+1]=min(x+1,y+1);
	    b[min(x+1,y+1)]++;
	}
	else if(a[x+1]!=0&&a[y+1]!=0&&a[y+1]!=a[x+1])
	{
		b[a[x+1]]=b[a[x+1]]+b[a[y+1]]+1;
		b[a[y+1]]=0;
		a[y+1]=a[a[x+1]];
	}
	else if((a[x+1]!=a[y+1])&&(a[x+1]!=0||a[y+1]!=0))
	{if(a[x+1]>0&&a[y+1]==0)
	{
	    a[y+1]=a[a[x+1]];
	    b[a[a[x+1]]]++;
	}
	else
	{a[x+1]=a[a[y+1]];b[a[a[y+1]]]++;
	}
	}
	}
	for(int i=1;i<=n;i++)count-=b[i];
	cout<<count<<endl;
	}
}
	return 0;
}

I don't know where it's fail plz some one suggest how to solve it as i have used all the concept of no of different trees in forest for this i have taken two vector
a for storing parent node and b for stroing no of connected node to parent one.

Suggested Topics

Topic Category Replies Views Activity
C and C++ 0 16 8d

Want to read more? Browse other topics in C and C++ or view latest topics.