459 - Graph Connectivity

[rio]

Your algorithm is still wrong.

Code: Select all

1

F
AB
BC
CA
DE
EF
FD

The answer should be 2, but your code ouputs 1.

Why don't you use DFS or BFS ?

And still there is a blank line after the last case.

[l314]

Hi, I used DFS to solve this problem and got AC.
thx a lot.

[Fuad Hassan EWU]

I am getting TLE in this problem,Why??? . I used DFS.

Code: Select all

ac

[A1]

I am getting TLE in this problem,Why??? . I used DFS.

you are getting TLE because of this part:

while(1){
gets(str);
if(str[0]==0)break;
......
......
}

as the problem statement says: Input is terminated by a blank line.
but i guess this last line contents some white space. so the while loop is running for ever..!!
so rewrite this part like:

while(gets(str)!=NULL){
if(str[0]==0 || str[0]==' '|| str[0]=='\n')break;
....
}

most probably this will resolve your TLE problem..
but you will get PE or WA.
because the problem says: The outputs of two consecutive cases will be separated by a blank line.
But you are giving a newline output at the beginning of every test case.

NB: it is better not using C input/output function (scanf, printf) with cin/cout of C++ . it could cause problem.

[Fuad Hassan EWU]

Thanks A1. now i got AC

[smilitude]

just needed to tell you that there wont be any test case like

Code: Select all

1

    E     
       AB         
         CE         
           DB          
          EC  

it will be given like this

Code: Select all

1

E     
AB         
CE         
DB          
EC 

so dont worry about this type of case!

[newton]

i cant undrstand why Compile Error?
please help me..

Code: Select all

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <queue>
#include <list>
#include <algorithm>
#define MAX 20000

using namespace std;

int numV;
queue<int> theQ;
list <int> L[MAX];
list<int>::iterator k;

int color[MAX];
void callBFS(int u);

void recolor(int n){
	for(int i = 0; i<n;i++){
		color[i] = 0;
	}
}

void flush(){
	while(!theQ.empty())
		theQ.pop();
}

int main()
{
	//freopen("in.txt","rt",stdin);
	int i,j,testCase;
	char edge[3];
	scanf("%d\n\n",&testCase);	
	for(i = 0; i < testCase; i++)
	{	
		if(i != 1)
			printf("\n");
		scanf("%c\n",&(int)numV);
		numV -= 'A'-1;

		for(j = 0; j < numV; j++){			
			L[j].clear();			
		}

		while(true){
			gets(edge);
			sscanf(edge,"%s",edge);
			if(!strcmp(edge,"\0"))
				break;
			
			L[int(edge[0] - 'A')].push_back(int(edge[1] - 'A'));
			L[int(edge[1] - 'A')].push_back(int(edge[0] - 'A'));
		}
				
		int num = 0;
		for(j = 0; j < numV; j++){						
			if(color[j] == 0){
				callBFS(j);
				num++;
			}
			
		}
		printf("%d\n",num);
		flush();
		recolor(numV);
	}		
	return 0;
}
void callBFS(int u){		
	theQ.push(u);
	color[u] = 1;
	while(!theQ.empty()){
		u = theQ.front();
		theQ.pop();					
		for(k = L[u].begin(); k != L[u].end(); ++k){
			if(color[*k] == 0){				
				theQ.push(*k);
				color[*k] = 1;
			}
		}
	}	
}

[jainal cse du]

Code: Select all

#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include <queue>
#define WHITE 0
#define GRAY 1
#define BLACK 2
using namespace std;

int graph[30][30];
int color[30];

void bfs(int source,int V)
{
	int i,u;
	
	queue<int>Q;
	color[source] = GRAY;	
	Q.push(source);
	while(!Q.empty())
	{
		u = Q.front();
		Q.pop();
		for(i = 0; i < V;i++)
		{
			if(graph[u][i] && color[i] == WHITE)
			{
				color[i] = GRAY;				
				Q.push(i);
			}
		}
		color[u] = BLACK;
	}
}

int main()
{
	
	
	freopen("in.txt","rt",stdin);
	char edge[100],str[5];
	int f,test,i,j,num;
	char largerNode;
	int maxNode;
	
	f = 0;
	scanf("%d\n",&test);
	while(test--)
	{
		if(f)
		{
			scanf("\n");
			printf("\n");
		}
		f = 1;
		scanf("%c\n",&largerNode);
		maxNode = largerNode - 64;
		for(i = 0; i < maxNode;i++)
			for(j = 0; j < maxNode; j++)
				graph[i][j] = 0;
			
		while(gets(edge))
		{
			if(!strcmp(edge,"\n") || !strcmp(edge,"\0") || !strcmp(edge," "))
				break;
			j = 0;
			for(i = 0; edge[i];i++)
			{
				if(isupper(edge[i]))
					str[j++] = edge[i];
			}
			edge[j] = NULL;
			int u = str[0] - 'A';
			int v = str[1] - 'A';
			graph[u][v] = 1;
			graph[v][u] = 1;
		}
		
		for(i = 0; i < maxNode;i++)
			color[i] = WHITE;
		num = 0;
		for(i = 0; i < maxNode; i++)
		{
				
			if(color[i] == WHITE)
			{
				bfs(i,maxNode);
				num++;
			}
				
		}
		printf("%d\n",num);
	}
	return 0;
}

I am getting WA.Please help me.

[jainal cse du]

I am tired with this stupid prob.
please someone checks my code.
I don't understand why OJ gives WA.

Code: Select all

Removed After AC.

[helloneo]

I am tired with this stupid prob.
please someone checks my code.
I don't understand why OJ gives WA.

Try this case..

Code: Select all

2

A

C
AB

My output is..

Code: Select all

1

2

[mak(cse_DU)]

To jainal,
compare your code with below code segment
See the change to take input of gets()// gets is very dangerous so I prefer scanf()

Code: Select all

char str[10000],max,*p,tmp[10];
   scanf("%d",&test);
   gets(str);
   gets(str);
   for(int i = 0; i < test; i++){      
      
	   
      if(i )
         printf("\n");
      scanf("%s",&tmp);
	  max=tmp[0];
      nV = max - 64;
	  gets(str);

Avoid pointer. you can use sscanf() to pickup string from a string. I got AC after this change

[jainal cse du]

Thanks MAK & Helloneo.
Now I got AC.

[sreejond]

ac

[ashraf24]

hi, i used bfs to solve this problem. i dont know why this code is getting RTE!!! plz help me ..
here is my code:

Code: Select all

#include <iostream>
#include <cstring>
#include <queue>
using namespace std;

#define MAX 26
int adj[MAX][MAX];
int color[MAX];
int maximum;

void init(void)
{
	int i,j;
	for(i=0;i<MAX;i++)
	{
		color[i] = 0;
		for(j=0;j<MAX;j++)
			adj[i][j] = 0;
	}
	return ;
}

void bfs(int start)
{
	int u;
	queue<int>Q;
	color[start] = 1;
	Q.push(start);
	while(!Q.empty())
	{
		u = Q.front();
		for(int i=0;i<=maximum;i++)
			if(adj[u][i] && !color[i])
			{
				Q.push(i);
				color[i] = 1;
			}
		Q.pop();
		color[u] = 2;
	}
	return ;
}

main()
{
	int test,i,total;
	char ch;
	char str[10];
	cin>>test;
	int flag = 1;
	while(test--)
	{
		scanf(" %c ",&ch);
		maximum = ch - 'A';
		init();
		while(gets(str))
		{
			if(!strcmp(str,"\n") || !strcmp(str,"\0") || !strcmp(str," "))
				break;
			adj[str[0]-'A'][str[1]-'A'] = adj[str[1]-'A'][str[0]-'A'] = 1;
		}
		for(i=0,total=0;i<maximum;i++)
			if(!color[i])
			{
				bfs(i);
				total++;
			}
		if(flag)
			cout<<total<<endl;
		else
			cout<<endl<<total<<endl;
		flag = 0;
	}
	return 0;
}

Thnx in advance...

[saiful_sust]

Can some one help me
I got WA......................

Code: Select all

Cut.....................