## 793 - Network Connections

Moderator: Board moderators

Spider
New poster
Posts: 4
Joined: Mon Aug 04, 2003 6:49 am

### 793. Why Wrong answer. HELP ME!!

Can anybody help me.

Code: Select all

``````var
i, j, n,m, ii, x, tmp,  y, scc, unscc : word;
c,tp : char;
graf : array [1..20000] of word;
q : word;
begin
for ii := 1 to m do
begin
q := 0;
scc := 0;
unscc := 0;
fillchar(graf,sizeof(graf),0);
while not (eoln or eof) do
begin
if (c = 'q') then
if (graf[x] = graf[y]) and (graf[x] <> 0) then
inc(scc)
else
inc(unscc)
else if (c = 'c') then
if (graf[x] = graf[y]) and (graf[x] = 0) then
begin
inc(q);
graf[x] := q;
graf[y] := q;
end
else if (graf[x] <> graf[y]) and (graf[x] = 0) then
graf[x] := graf[y]
else if (graf[x] <> graf[y]) and (graf[y] = 0) then
graf[y] := graf[x]
else if (graf[x] <> graf[y]) then
begin
tmp := graf[y];
for i := 1 to n do
if (graf[i] = tmp) then
graf[i] := graf[x];
end;
end;
writeln(scc,',',unscc);
if (ii <> m) then writeln;
end;

end.``````

Faizur
New poster
Posts: 39
Joined: Fri Jun 06, 2003 3:04 pm
I have solved this problem using dfs. which is a rather too slow.
Where Can I get the reference of union find algorithm?

wyanez
New poster
Posts: 8
Joined: Thu Nov 20, 2003 7:19 pm

### Union and Find

Test in google using like key words:
union find algorithm
I found alli good information

Experienced poster
Posts: 131
Joined: Thu Aug 14, 2003 10:23 pm
Location: BUET
Contact:

### 793,problem taking input

i am receiving WA all the time . i guess i am having prob taking input and handle multiple input .

****is there some input for which my output is wrong ??? may i missing some thing ??? pliz help me in this code ..........

[cpp]#include<stdio.h>
#include<stdlib.h>

int p[10000];
int sucks;

void init(){

int i ;

for(i=0;i<(sucks+1);i++){
p=-1;
}

}

int Query(int x , int y){

if(p[x]==p[y])
return 1;
else
return 0;
}

void update(int to , int with){

int i ;

for(i=0;i<(sucks+1);i++){

if(p==-1)continue;
else if(p==to)p=with;
}

}

void Insert(int x , int y ){

int m , n ;
if(p[x]==-1 && p[y]==-1)
p[x]=p[y]=x;
else if(p[x]==-1 && p[y]!=-1)
p[x]=p[y];
else if(p[x]!=-1 && p[y]==-1)
p[y]=p[x];
else if(p[x]!=-1 && p[y]!=-1){

m=p[x];
n=p[y];

p[y]=n;

update(m,n);
}

}

int main(){

char in[1000];
int x , y;
char ch;
int ans ;

int success , unsuccess;
/*for multiple input */
int minput ;
/*-------------------*/

freopen("input.txt","r",stdin);

gets(in);
minput=atoi(in);

gets(in);
while(minput>0){

//gets(in);

gets(in);

sucks=atoi(in);

init();
success = unsuccess = 0;

while(gets(in) && sscanf(in,"%c %d %d",&ch,&x,&y)==3){

//sscanf(in,"%c %d %d",&ch,&x,&y);

if(ch=='q'){

ans=Query(x,y);

if(ans==0)
unsuccess++;

else if(ans==1)

success++;

}

else if(ch=='c'){

Insert(x,y);

}

}

printf("%d,%d\n",success,unsuccess);

minput--;

if(minput)
printf("\n");
}

return 0;
}[/cpp]

Bye
HOLD ME NOW ,, I AM 6 FEET FROM THE EDGE AND I AM THINKIN.. MAY BE SIX FEET IS SO FAR DOWN

sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York
I have scrutinize your code and -

1) Your handling of the input data is perfectly alright.
2) Infact it is the best way.

I have made few modifications to your code and got it AC.
When initializing the array don't use -1, use the index number itself.
I mean
for (i=0;i<sucks+1;i++)
P[i] = i;

And using this method you don't have to check for -1 in your query function.
Hope it helps.

------------------------------------------------------------------------------------
--One learns the most by helping others.

Experienced poster
Posts: 131
Joined: Thu Aug 14, 2003 10:23 pm
Location: BUET
Contact:

### help help !!!!!!!!!!!!!!!

hey sohel ,
i did not get u r second part of reply . that i dont have to check -1 in the function query .
And using this method you don't have to check for -1 in your query function.
i got the initialization part , that to initialize with index rather than -1 .

help me plizzzzzzzzzzzzzz
Bye
HOLD ME NOW ,, I AM 6 FEET FROM THE EDGE AND I AM THINKIN.. MAY BE SIX FEET IS SO FAR DOWN

sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York
In your query function - you coded

if(p[x]==p[y])
return 1;

In your code if p[x] and p[y] are -1 then the function will return 1;
but it should return 0;

But if you initialize with 'index' , this case will be treated automatically.
[/c][/code]

Experienced poster
Posts: 131
Joined: Thu Aug 14, 2003 10:23 pm
Location: BUET
Contact:
hey sohel ,
thanx once again for replying . i have changed my query function to tackle the problem u mentioned . but i am still getting WA .

My Changed Query Function is :-

[cpp]void init(){

int i ;

for(i=0;i<(sucks+1);i++){
p=-1;
}

}

int Query(int x , int y){

if((p[x]!=-1 && p[y]!=-1) && (p[x]==p[y]))
return 1;
else
return 0;
}[/cpp]

My Term Final Exam is near . so i cant give enough time for debugging the problem . Sorry if i made Any Stupid Mistake . Plizzzzzzzz Help Me In This .
Thanx Sohel
Bye
HOLD ME NOW ,, I AM 6 FEET FROM THE EDGE AND I AM THINKIN.. MAY BE SIX FEET IS SO FAR DOWN

Experienced poster
Posts: 131
Joined: Thu Aug 14, 2003 10:23 pm
Location: BUET
Contact:

### Hey Some One Help Me In 793,,, WA all the time

hey is there some one who could help me in 793 ? i am getting wa all the time . in the previous post sohel mentioned a bug which i guess i got fixed . but still i am getting WA all the time . plizzzzzzzz help me in this . is there any tricky input ?????????????here is some portion of my QUERY and UPDATE function .all the other codes r unchanged .

[cpp]void init(){

int i ;

for(i=0;i<(sucks+1);i++){
p=-1;
}

}

int Query(int x , int y){

if((p[x]==p[y]) && p[x]!=-1 && p[y]!=-1)
return 1;
else
return 0;
}

void update(int to , int with){

int i ;

for(i=0;i<(sucks+1);i++){

if(p==-1)continue;
if(p==to)p=with;
}

}

void Insert(int x , int y ){

int m , n ;
if(p[x]==-1 && p[y]==-1)
p[x]=p[y]=x;
else if(p[x]==-1 && p[y]!=-1)
p[x]=p[y];
else if(p[x]!=-1 && p[y]==-1)
p[y]=p[x];
else if(p[x]!=-1 && p[y]!=-1){

m=p[x];
n=p[y];

p[y]=n;

update(m,n);
}

}[/cpp]

Bye
HOLD ME NOW ,, I AM 6 FEET FROM THE EDGE AND I AM THINKIN.. MAY BE SIX FEET IS SO FAR DOWN

miras
Learning poster
Posts: 98
Joined: Sat Jun 14, 2003 1:45 pm
look...

Multiple input....

num of tests
[space]
test1
[space]
.
.
.

and so on...
Remember Never Give Up
Miras

New poster
Posts: 14
Joined: Sat Jul 03, 2004 1:18 pm
Contact:

### 793 the dfs giving WA,Why?

I tried with the following code,based on dfs.
what is the critical input with respect to my code.

C code:

#include<stdio.h>
void dfs(int v);

void dfs(int v)
{
int i,w;
color[v]=1;
if(v==b) f=1;
if(f==1) return;
for(i=1;i<=len[v];i++)
{
if(color[w]==0)
{
dfs(w);
}
if(f) break;
}
}
main()
{
long double s,us;
unsigned long x,i,j;
int m[1001][1001];
char c,c1,c2;

scanf("%lu",&x);
while(x!=0){x--;
scanf("%d%c",&n,&c);
s=us=0;
for(i=1;i<=n;i++)
{len=0;for(j=i;j<=n;j++) m[j]=m[j]=0;}
while(1)
{
scanf("%c",&c1);
while(c1==' ') {scanf("%c",&c1);}
if(c1=='\n') break;
scanf("%d %d",&a,&b);
if(c1=='c')
{
m[a]=m[a]=1;
}
else if(c1=='q')
{
for(i=1;i<=n;i++)
color=0;
f=0;
if(a==b)
{
if(m[a][a]==1||len[a]!=0) s++;
else us++;
}
else
{
dfs(a);
if(color==1) s=s+1;
else us=us+1;
}
}
j=scanf("%c",&c2);
if(j==EOF) break;
}
printf("%.0Lf,%.0Lf\n",s,us);
if(x!=0) printf("\n");
}
}
sobhani

Ivo Sluganovic
New poster
Posts: 12
Joined: Tue Sep 21, 2004 10:08 pm

### 793 Network Connections WA, what am I doing wrong?

I get WA, but don't have any idea why!
Is something wrong with my input?

Code: Select all

``````
int main(void)
{
int i, n, t, a, b, suc, unsuc, c;

scanf("%d", &t);

for(; t>0; t--){
suc = 0 ;
unsuc = 0;

scanf("%d\n", &n);

for(i=0; i<=n; i++)

for( ; ; ){
c = getc(stdin);

if (c != 'c' && c != 'q')
break;

scanf("%d%d\n", &a, &b);

if (c == 'c')
find(a, b, 1);
else
if (!find(a, b, 0))
unsuc++;
else
suc++;
}

printf("%d,%d\n", suc, unsuc);
}

return 0;
}

``````
THX!!!
Last edited by Ivo Sluganovic on Mon Jan 31, 2005 6:06 pm, edited 1 time in total.

Ghust_omega
Experienced poster
Posts: 115
Joined: Tue Apr 06, 2004 7:04 pm
Location: Venezuela
Hi !! Ivo Sluganovic try this Input
Input:

Code: Select all

``````2

10
c 1 5
c 2 7
q 7 1
c 3 9
q 9 6
c 2 5
q 7 5

10
c 1 5
c 2 7
q 7 1
c 3 9
q 9 6
c 2 5
q 7 5
``````
Ouput:

Code: Select all

``````1,2

1,2
``````

Code: Select all

``````1,2
2,1
``````
Hope it helps
Keep posting !!

Ivo Sluganovic
New poster
Posts: 12
Joined: Tue Sep 21, 2004 10:08 pm
I got AC.

I reallized where the problem was and solved it by changing the for loop to look like this:
for(i=0; i<MAXN; i++)

This works, because N is actually irrelevant, but what should I do to scanf N correctly?
Could you explain me why my older code didn't work?

Thank you very much!

sql_lall
New poster
Posts: 2
Joined: Thu Sep 30, 2004 8:38 am
Contact:

### 793 - WA problem

Code: Select all

``````#include <cstdio>
#include <vector>
using std::vector;

const int MAXN = 99999;
int label[MAXN];
char buffer[MAXN];

int find(int x) {
int y = x;
while (label[y] != y) y = label[y];
while (label[x] != x) {
int z = label[x];
label[x] = y;
x = z;
}
return y;
}

int main()
{
int T;
scanf("%d\n", &T);
while(T--){
int N;
scanf("%d\n", &N);
for(int i = 0; i < MAXN; i++) label[i] = i;
char t;
int a, b, N1, N2;
N1 = N2 = 0;

gets(buffer);
while(strlen(buffer) != 0){
sscanf(buffer, "%c %d %d\n", &t, &a, &b);
if(t == 'q'){
int fa = find(a);
int fb = find(b);
if(fa == fb) N1 ++;
else         N2 ++;
} else {
if(a > b) a ^= b ^= a ^= b;
int fa = find(a);
int fb = find(b);
label[fa] = fb;
}
if(feof(stdin) || strlen(buffer) == 0) break;
gets(buffer);
}
printf("%d,%d\n", N1, N2);
if(T != 0) printf("\n");
}
return 0;
}``````
I've been away from this type of programming for a while, so am probably missing an obvious bug, but can anyone spot the error? It's not in the input parsing, i believe.
- sql_lall