Tle in cam5

[so_what_sof]

hi ,
actually I am trying to solve problem CAM5 spoj.com/problems/CAM5/ by using bfs , what am i doing is i take the undirect graph as a adjncey list and call the bfs function
and count how many times queue get empty and increment the count ... but this leads to me tle ,please give me the right way to solve this .. thank you

/** my program**/
#include<stdio.h>
#include<algorithm>
#include<queue>
#include<iostream>
#include<cstring>
#include<cmath>
#include<string.h>
#include<map>
#include<vector>
#include<list>
#include<limits.h>
using namespace std;
void traverse(vector<list<long long int> >my_vector)
{
	cout<<"\n";
	long long int c=0;
	for(vector<list<long long int> >::iterator i=my_vector.begin();i!=my_vector.end();++i)
{
	cout<<c<<" ";
	list<long long int>l=*i;
	for(list<long long int>::iterator j=l.begin();j!=l.end();++j)
	{
		cout<<(*j)<<" ";
		}//end of the inner for loop
		cout<<"\n";
	c++;
	}//end of the outer for loop
	}//end of the traverse function
	void compute_bfs(vector<list<long long int> >my_vector,vector<long long int>another_vector)
	{
		long long int node=0;
		long long int count1 =1;
		long long int arr[100001]={0};
		queue<long long int> q;
		q.push(node);
		while(!another_vector.empty())
		{
		while(!q.empty())
		{
		//push all the adjacent in the node
		vector<list<long long int> >:: iterator i;
		i=my_vector.begin();
		advance(i,q.front());
		list<long long int>l=*i;
		for(list<long long int>::iterator j=l.begin();j!=l.end();++j)
		{
			if(arr[q.front()]==0)
			{
				q.push((*j));
				}//end of the if statemrnt
			}//end of the inner for loop
			if(arr[q.front()]!=1)
			//cout<<q.front()<<" ";
			arr[q.front()]=1;
//			another_vector.erase(std::remove(another_vector.begin(), another_vector.end(), q.front()), another_vector.end());
			another_vector.erase(std::remove(another_vector.begin(), another_vector.end(), q.front()), another_vector.end());
			q.pop();
				}//end of the while function
	count1=count1+1;
	//cout<<count1<<"\n";
	//for(int i=0;i<another_vector.size();i++)
	//cout<<another_vector[i]<<" ";
	//cout<<"\n";
	q.push(another_vector[0])	;
	}//end of the while loop
		cout<<count1-1<<"\n";
		}//end of the compute_bfs function
int main()
{
	int t=0;
	scanf("%d",&t);
	while(t>0)
	{
		long long int node=0,edge=0,c=0;
		scanf("%lld%lld",&node,&edge);
		c=edge;
		vector<list<long long int> >my_vector(node+1);
		vector<long long int> another_vector;
		for(long long int i=0;i<node;i++)
		another_vector.push_back(i);
		while(edge>0)
		{
			long long int source=0,dest=0;
			scanf("%lld%lld",&source,&dest);
			my_vector[source].push_back(dest);
			my_vector[dest].push_back(source);
			edge--;
			}//end of the while loop
//traverse(my_vector);		
if(c==0)cout<<node<<"\n";
else
compute_bfs(my_vector,another_vector);
t=t-1;
		}//end of the while lioop
	//system("pause");
	return 0;
	}//end of the main function

[leppyr64]

Please use code tags when posting code.

[so_what_sof]

I ill remember it from next time but will you please clear my doubt

[leppyr64]

Removing items from Vectors has a large complexity due to the memory reallocations.

You could simply use an array to flag whether or not a node has been pushed onto the queue or not.

for node = 1 to number of nodes
  if node is not visited then
    bfs(node) and increment count
next i

Also, why are you using long long?

[so_what_sof]

I am trying according to you but still getting tle ,please find if any thing wron with my new code

#include<stdio.h>
#include<algorithm>
#include<queue>
#include<iostream>
#include<cstring>
#include<cmath>
#include<string.h>
#include<map>
#include<vector>
#include<list>
#include<limits.h>
using namespace std;
void traverse(vector<list<long long int> >my_vector)
{
	cout<<"\n";
	long long int c=0;
	for(vector<list<long long int> >::iterator i=my_vector.begin();i!=my_vector.end();++i)
{
	cout<<c<<" ";
	list<long long int>l=*i;
	for(list<long long int>::iterator j=l.begin();j!=l.end();++j)
	{
		cout<<(*j)<<" ";
		}//end of the inner for loop
		cout<<"\n";
	c++;
	}//end of the outer for loop
	}//end of the traverse function
	void compute_bfs(vector<list<int> >my_vector, int node,int arr[])
	{
		queue<int> q;
		q.push(node);
		while(!q.empty())
		{
		//push all the adjacent in the node
		vector<list< int> >:: iterator i;
		i=my_vector.begin();
		advance(i,q.front());
		list< int>l=*i;
		for(list< int>::iterator j=l.begin();j!=l.end();++j)
		{
			if(arr[(*j)]!=(*j))
			{
				q.push((*j));
				arr[(*j)]=(*j);
				}//end of the if statemrnt
			}//end of the inner for loop
			arr[q.front()]=q.front();
			q.pop();
		}
    	}//end of the compute_bfs function
int main()
{
	int t=0;
	scanf("%d",&t);
	while(t>0)
	{
		 int node=0,edge=0,c=0;
		scanf("%d%d",&node,&edge);
		c=edge;
		vector<list<int> >my_vector(node+1);
		 int arr[100001]={0};
		while(edge>0)
		{
			 int source=0,dest=0;
			scanf("%d%d",&source,&dest);
			my_vector[source].push_back(dest);
			my_vector[dest].push_back(source);
			edge--;
			}//end of the while loop		
			 int count=1;
			if(c==0)
			printf("%d\n",node);
			else
			{
for( int i=0;i<node;i++)
{
	if(arr[i]==0)
	{
		//mark it
		arr[i]=1;
		compute_bfs(my_vector,i,arr);
		count++;
	}//end of the if
	}//end of the for loop
printf("%d\n",(count-1));
}
t--;
}
	return 0;
	}//end of the main function

[leppyr64]

Why are you using long long?

[so_what_sof]

i am using int not long long that traverse function is not called so no sense of tle beacuse of that...further i use int.
tell me if my method is right

[leppyr64]

arr[i]=1;

if(arr[(*j)]!=(*j))

[so_what_sof]

accepted!!!! change my bfs function and instead of using vector> i used vector.....