Page **4** of **9**

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

Posted: **Mon Apr 24, 2006 1:12 pm**

by **serur**

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?

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

Posted: **Mon Apr 24, 2006 1:48 pm**

by **helloneo**

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

Posted: **Mon Apr 24, 2006 9:13 pm**

by **serur**

Thank you Helloneo for your reply!

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!

Posted: **Tue Jun 06, 2006 1:57 am**

by **Jan**

Edit : I have to look it again.

### more input

Posted: **Thu Jul 06, 2006 5:14 pm**

by **yin_yang2k**

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?

**[edit]***(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)

Posted: **Thu Jul 06, 2006 5:17 pm**

by **yin_yang2k**

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.

**[edit]** got

Accepted and I still get this output, (removed the last new line because it gave PE)

**[/edit]**

Posted: **Thu Jul 06, 2006 8:39 pm**

by **Ghust_omega**

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

Posted: **Thu Jul 06, 2006 8:42 pm**

by **Ghust_omega**

by the way your ouput is fine my program give the same answers

Hope it helps

Keep Posting

Posted: **Fri Jul 07, 2006 2:15 pm**

by **yin_yang2k**

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!

Posted: **Fri Jul 07, 2006 3:05 pm**

by **Ghust_omega**

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

### Problem with this problem

Posted: **Mon Jul 10, 2006 6:48 am**

by **smilitude**

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?

Posted: **Tue Oct 17, 2006 3:53 am**

by **tuman**

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.

### 459 WA

Posted: **Sat Feb 10, 2007 6:38 pm**

by **l314**

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;
string read;
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){
getline(cin, read);
read.erase(remove(read.begin(), read.end(), ' '), read.end());
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.

Posted: **Sat Feb 10, 2007 7:04 pm**

by **rio**

Your algorithm is wrong. Consider this case.

This graph is

but your code answers 2.

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.

Posted: **Sat Feb 10, 2007 8:39 pm**

by **l314**

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;
string read;
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){
getline(cin, read);
read.erase(remove(read.begin(), read.end(), ' '), read.end());
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;
}
```