Page 4 of 9

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

Posted: Mon Apr 24, 2006 1:12 pm
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
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
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
Edit : I have to look it again. ### more input

Posted: Thu Jul 06, 2006 5:14 pm
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?
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
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

``````

Posted: Thu Jul 06, 2006 8:39 pm
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,*res2;//this is for take the input

initialize_graph(g);//fluhs the graph
gets(c);//get the line
sscanf(c,"%c",&c);//I scan for the firts caracter
i = c-'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 - 'A');//see the node origin
y = (int)(c - '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 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
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
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
My main function looks like this, I used union-find data struct;

Code: Select all

``````int main() {
int cases;
int i,j;
char line;
bool check;
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
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
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={0};

cin>>turn;
cout<<endl;
while(turn--){
ans = 0;
cin>>c;
cin.ignore();
size = c - '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){

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

Posted: Sat Feb 10, 2007 8:39 pm
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

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={0};

cin>>turn;
while(turn--){
ans = 0;
cin>>c;
cin.ignore();
size = c - '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){

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

``````