## 459 - Graph Connectivity

All about problems in Volume 4. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan
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
New poster
Posts: 7
Joined: Sun Jan 28, 2007 9:53 am
Hi, I used DFS to solve this problem and got AC.
thx a lot.

New poster
Posts: 38
Joined: Tue Jul 17, 2007 3:21 pm
Location: East West University

### TLE

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

Code: Select all

``````ac
``````
Last edited by Fuad Hassan EWU on Tue Oct 30, 2007 7:35 pm, edited 1 time in total.
Eagle er moto daana meley urbo

A1
Experienced poster
Posts: 173
Joined: Wed Jan 28, 2004 3:34 pm

### Re: TLE

Fuad Hassan EWU wrote: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.

New poster
Posts: 38
Joined: Tue Jul 17, 2007 3:21 pm
Location: East West University

### THANKS

Thanks A1. now i got AC
Eagle er moto daana meley urbo

smilitude
Experienced poster
Posts: 137
Joined: Fri Jul 01, 2005 12:21 am

### Re: 459 - WA

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

``````
fahim
#include <smile.h>

newton
Experienced poster
Posts: 162
Joined: Thu Jul 13, 2006 7:07 am
Location: Campus Area. Dhaka.Bangladesh
Contact:

### Re: 459 - WA

i cant undrstand why Compile Error?

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
New poster
Posts: 23
Joined: Thu Jul 27, 2006 2:43 pm
Location: University of Dhaka,Bangladesh

### Re: 459 - WA

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;
}

``````

jainal cse du
New poster
Posts: 23
Joined: Thu Jul 27, 2006 2:43 pm
Location: University of Dhaka,Bangladesh

### Re: 459 - Graph Connectivity

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.
``````
Last edited by jainal cse du on Sun Sep 14, 2008 10:24 pm, edited 1 time in total.

helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea

### Re: 459 - Graph Connectivity

jainal cse du wrote: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)
Learning poster
Posts: 72
Joined: Tue May 30, 2006 5:57 pm

### Re: 459 - Graph Connectivity

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
Mak
Help me PLZ!!

jainal cse du
New poster
Posts: 23
Joined: Thu Jul 27, 2006 2:43 pm
Location: University of Dhaka,Bangladesh

### Re: 459 - Graph Connectivity

Thanks MAK & Helloneo.
Now I got AC.

sreejond
New poster
Posts: 32
Joined: Fri May 23, 2008 6:16 pm
Contact:

### 459-TLE???

ac
Last edited by sreejond on Fri Jun 05, 2009 9:20 pm, edited 1 time in total.

ashraf24
New poster
Posts: 1
Joined: Fri Nov 21, 2008 10:08 pm

### Re: 459 - Graph Connectivity

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 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++)
}
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++)
{
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;
}
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;
}``````

saiful_sust
Learning poster
Posts: 97
Joined: Fri Aug 22, 2008 10:18 pm
Location: CSE.SUST.SYLHET

### Re: 459 - Graph Connectivity

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

Code: Select all

``````Cut.....................
``````