## 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

serur
A great helper
Posts: 251
Joined: Thu Feb 23, 2006 11:30 pm

### 459- DFS(Floodfill) => WA!

Hello Fellows!

The Problem is in 459-"Graph Connectivity". OJ responds "WA".
The problem is in finding how many connected componentns are there in given non-oriented graph, isn't it? Then it can be solved by DFS?
My algo:
after parsing input I run a loop from 'A' to the "the largest node name in the graph" and for every symbol(node of a graph) check whether it is visited or not. If not visited, I increment component_counter by 1 and floodfill the connected component.
Also, how should one benefit if uses solution based on Disjoit-Set data structure instead of DFS?

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

### Re: 459- DFS(Floodfill) => WA!

serur wrote:Hello Fellows!

The Problem is in 459-"Graph Connectivity". OJ responds "WA".
The problem is in finding how many connected componentns are there in given non-oriented graph, isn't it? Then it can be solved by DFS?
My algo:
after parsing input I run a loop from 'A' to the "the largest node name in the graph" and for every symbol(node of a graph) check whether it is visited or not. If not visited, I increment component_counter by 1 and floodfill the connected component.
Also, how should one benefit if uses solution based on Disjoit-Set data structure instead of DFS?
You're algo seems to be alright.. don't know why WA ..
and "Union-Find" is maybe faster than DFS..

I got TLE for the problem "793 - Network Connections " with your algorithm.. but I re-coded with "Union-Find" and then I got AC..

serur
A great helper
Posts: 251
Joined: Thu Feb 23, 2006 11:30 pm
The problem was in assuming that input is nicely formatted, it's so stupid of me to be trapped in such a way! Now AC.
Well, I should think about Union-Find, its implementation and elaboration.
Thank you!

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Contact:
Edit : I have to look it again.
Last edited by Jan on Tue Oct 24, 2006 11:54 pm, edited 1 time in total.
Ami ekhono shopno dekhi...
HomePage

yin_yang2k
New poster
Posts: 4
Joined: Wed Jul 05, 2006 6:50 pm
Location: Sweden

### more input

I am getting WA on this problem. Can someone with a AC code try the input on the next post and share the result with us who needs it ?
My code is generating 2 new lines when it outputs the last case, could that be the error?
(code link removed, got accepted)[/edit]
I'm new to C++ and just learned about that you have to delete objects that you create. (Witch you don't have to in Java)
Last edited by yin_yang2k on Fri Jul 07, 2006 2:22 pm, edited 3 times in total.

yin_yang2k
New poster
Posts: 4
Joined: Wed Jul 05, 2006 6:50 pm
Location: Sweden
Please post your result for this input. (If you have a AC code that is )

INPUT

Code: Select all

``````10

E
AB
CE
DB
EC

Z
AB
CF

A
ZY
WS
PQ

D
AA
BB
CC
DD

E
AB
BA
AB
BA

Z
AB
BC
CD
DE
EF
FG
GH
HI
IJ
JK
KL
LM
MN
NO
OP
PQ
QR
RS
ST
TU
UV
VW
WX
XY
YZ

A

M

Z

I
AI
BI
CI
DI
IE
IF
IG
IH``````
My WA code output, and yes those two new lines at the end is something my code does.
 got Accepted and I still get this output, (removed the last new line because it gave PE) [/edit]

Code: Select all

``````2

24

1

4

4

1

1

13

26

1

``````
Last edited by yin_yang2k on Fri Jul 07, 2006 2:23 pm, edited 2 times in total.

Ghust_omega
Experienced poster
Posts: 115
Joined: Tue Apr 06, 2004 7:04 pm
Location: Venezuela
Hi !! yin_yang2k

I will go to post mi algorithm for take the input cause the algorithm for get the answer is easy, is just take the components conex.

Code: Select all

``````int read_graph(graph *g)
{
int i,j,p,x,y,res1;
char c[10],*res2;//this is for take the input

initialize_graph(g);//fluhs the graph
gets(c);//get the line
sscanf(c,"%c",&c[0]);//I scan for the firts caracter
i = c[0]-'A';
g->nvertices = i+1;

for(j=0;j<i+1;j++)
visited[j]=false;
p=0;
while(1){
res2=gets(c);
res1=sscanf(c,"%s",c);
if(res1==EOF || res2==NULL)//if there is nothing break
break;
x = (int)(c[0] - 'A');//see the node origin
y = (int)(c[1] - 'A');//see the destiny
insert_edge(g,x,y,0);//insert edge in the graph
}
return 1;
}
``````
Hope that helps
Keep posting

Ghust_omega
Experienced poster
Posts: 115
Joined: Tue Apr 06, 2004 7:04 pm
Location: Venezuela
by the way your ouput is fine my program give the same answers

Hope it helps
Keep Posting

yin_yang2k
New poster
Posts: 4
Joined: Wed Jul 05, 2006 6:50 pm
Location: Sweden
Thanks Ghust_omega!

I remade my input algorithm to look like yours and I got Presentation Error (Accepted). Then after some work with the new lines in my output algorithm I got accepted. I didn't touch my algorithm that solves the problem so it was al about the input algorithm.

I often have problem with the input and output with C++. Is there a thread in the forum about how to read input in C++ ?
I hope UVA will get a newer Java version soon

tnx again!

Ghust_omega
Experienced poster
Posts: 115
Joined: Tue Apr 06, 2004 7:04 pm
Location: Venezuela
Hi !! yin_yang2k

Is good see that your problem is fine, for the problems of the input in c++ I used a mix between C and C++ for the read input because I consider that C has better read and out that C++, sometimes is uncorfortable write cout<< and << and <<...... etc. but is a opinion very personal, so I use C for the input and C++ for code the rest. Here in the board you can find a chapter dedicated to C++ see if there any topic about the input.

Hope it helps
Keep posting

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

### Problem with this problem

My main function looks like this, I used union-find data struct;

Code: Select all

``````int main() {
int cases;
int i,j;
char line[1000];
bool check[30];
char ch,a,b;
int n;
int count;
bool print=false;
int len;

cin>>cases;
cin.getline(line,255);
cin.getline(line,255); //garbage
while(cases--) {
cin>>ch;
cin.getline(line,255); //garbage
n=ch-'A';
for(i=0;i<=n;i++) makeset(i);
memset(check, false , sizeof(check));
count=0;
while(true) {
cin.getline(line,255);
if(!strcmp(line,"")) break;
len=strlen(line);
for(i=0;i<len;i++)
if(line[i]>='A' && line[i]<='Z') {
a=line[i];
i++;
break;
}
for(;i<len;i++)
if(line[i]>='A' && line[i]<='Z') {
b=line[i];
break;
}

setunion(a-'A',b-'A');
}
for(i=0;i<=n;i++)
check[p[i]]=true;
for(i=0;i<=n;i++)
if(check[i]) count++;
if(print) cout<<endl;
cout<<count<<endl;
print=true;
}
//system("pause");
return 0;
}
``````
This works fine for all the IO in this thread, but still WA.
May I ask for some IO, or some suggestion plz?
fahim
#include <smile.h>

tuman
New poster
Posts: 24
Joined: Sat Oct 22, 2005 7:30 pm
Location: CUET
Contact:
After a long time
Sorry jAn it didnt solve the matter. Still run time error. This time your prediction didnt click. Why dont u ve another look at it? I hv done this typo of problem b4. But i guess i ve some problem in taking input here.
We the dreamer of the dreamy dream...

l314
New poster
Posts: 7
Joined: Sun Jan 28, 2007 9:53 am

### 459 WA

Hi,I get WA all the time, I don't know why!!

I have tried all the input cases of below threads.
(my code got the the same output)
http://online-judge.uva.es/board/viewto ... 7467f8212e
http://online-judge.uva.es/board/viewto ... d76eef7fe2

My source:

Code: Select all

``````#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

int main(){
int turn, size, n1, n2, ans;
char node1,node2;
string c;
bool visted[26]={0};

cin>>turn;
cout<<endl;
while(turn--){
ans = 0;
cin>>c;
cin.ignore();
size = c[0] - 'A'+1;
bool table[size][size];
bool flag;

for(int i=0; i<size; i++)
for(int j=0; j<size; j++)
table[i][j] = false;

while(1){

if( read.empty() == true || read[0] == '\0')
break;
n1 = read[0] - 'A';
n2 = read[1] - 'A';
if(n1 != n2){
table[n1][n2] = true;
table[n2][n1] = true;
}
}

for(int i=0; i<size; i++){
flag = false;
for(int j=0; j<size; j++){
if(table[i][j] == true){
if(visted[j] == true)
flag = true;
else
visted[j] = true;
}
}
if(visted[i] == false && flag == false)
++ans;
}

cout<<ans<<endl;
cout<<endl;
for(int i=0;i<size;i++)
visted[i]= false;
}
return 0;
}

``````
plz help me, thx.
Last edited by l314 on Sat Feb 10, 2007 7:10 pm, edited 1 time in total.

rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan
Your algorithm is wrong. Consider this case.

Code: Select all

``````1

E
AE
EC
CB
BD
``````
This graph is

Code: Select all

``A - E - C - B - D``

Your output format is wrong too.
The outputs of two consecutive cases will be separated by a blank line.
Don't print a blank line before the first case, and after the last case.
----
ADD : Don't open a new thread if it already exist for the problem.

l314
New poster
Posts: 7
Joined: Sun Jan 28, 2007 9:53 am
Hi, I fixed my algorithm so that it can output correctly for your input case and all cases from below links, but I still get WA.
http://online-judge.uva.es/board/viewto ... 7467f8212e
http://online-judge.uva.es/board/viewto ... d76eef7fe2

Thank for your help.

My new source:

Code: Select all

``````#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

int main(){
int turn, size, n1, n2, ans, max;
char node1,node2;
string c;
bool visted[26]={0};

cin>>turn;
while(turn--){
ans = 0;
cin>>c;
cin.ignore();
size = c[0] - 'A'+1;
bool table[size][size];

for(int i=0; i<size; i++)
for(int j=0; j<size; j++)
table[i][j] = false;

while(1){

if( read.empty() == true || read[0] == '\0')
break;
n1 = read[0] - 'A';
n2 = read[1] - 'A';
if(n1 != n2){
if(n1 > n2)
table[n1][n2] = true;
else
table[n2][n1] = true;
}
}

for(int i=1; i<size; i++){
for(int j=0; j<i; j++){
if(table[i][j] == true){
if(visted[j]==true)
visted[i] = true;
else
visted[j] = true;
}
}
}

for(int i=0; i<size; i++){
if(visted[i] == false)
++ans;
}

if(ans == 0)
++ans;
cout<<ans<<endl;
if(turn != 1)
cout<<endl;
for(int i=0;i<size;i++)
visted[i]= false;
}
return 0;
}

``````