## 793 - Network Connections

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

Moderator: Board moderators

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

Can anybody help me.
Why I get wrong answer?????????????????????????

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   readln(m);   for ii := 1 to m do   begin   q := 0;   scc := 0;   unscc := 0;   fillchar(graf,sizeof(graf),0);   readln(n);   while not (eoln or eof) do   begin      read(c);      readln(x,y);      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.`
Spider
New poster

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

I have solved this problem using dfs. which is a rather too slow.
Where Can I get the reference of union find algorithm?
Faizur
New poster

Posts: 39
Joined: Fri Jun 06, 2003 3:04 pm

### Union and Find

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

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

### 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[i]=-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[i]==-1)continue;
else if(p[i]==to)p[i]=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
Riyad
HOLD ME NOW ,, I AM 6 FEET FROM THE EDGE AND I AM THINKIN.. MAY BE SIX FEET IS SO FAR DOWN

Riyad
Experienced poster

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

Hi Riyad,
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.

sohel
Guru

Posts: 865
Joined: Thu Jan 30, 2003 5:50 am
Location: University of Texas at San Antonio

### 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
Riyad
HOLD ME NOW ,, I AM 6 FEET FROM THE EDGE AND I AM THINKIN.. MAY BE SIX FEET IS SO FAR DOWN

Riyad
Experienced poster

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

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]

sohel
Guru

Posts: 865
Joined: Thu Jan 30, 2003 5:50 am
Location: University of Texas at San Antonio

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[i]=-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
Riyad
HOLD ME NOW ,, I AM 6 FEET FROM THE EDGE AND I AM THINKIN.. MAY BE SIX FEET IS SO FAR DOWN

Riyad
Experienced poster

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

### 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[i]=-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[i]==-1)continue;
if(p[i]==to)p[i]=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
Riyad
HOLD ME NOW ,, I AM 6 FEET FROM THE EDGE AND I AM THINKIN.. MAY BE SIX FEET IS SO FAR DOWN

Riyad
Experienced poster

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

look...

Multiple input....

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

and so on...
Remember Never Give Up
Regrads
Miras
miras
Learning poster

Posts: 98
Joined: Sat Jun 14, 2003 1:45 pm

### 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.
Some please help me.

C code:

#include<stdio.h>
void dfs(int v);
int a,b,f,n,adj[1001][1001],len[1001],color[1001];

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++)
{
w=adj[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[i]=0;for(j=i;j<=n;j++) m[i][j]=m[j][i]=0;}
while(1)
{
scanf("%c",&c1);
while(c1==' ') {scanf("%c",&c1);}
if(c1=='\n') break;
scanf("%d %d",&a,&b);
if(c1=='c')
{
if(m[a][b]==0) adj[a][++len[a]]=b;
if(m[b][a]==0) adj[b][++len[b]]=a;
m[a][b]=m[b][a]=1;
}
else if(c1=='q')
{
for(i=1;i<=n;i++)
color[i]=0;
f=0;
if(a==b)
{
if(m[a][a]==1||len[a]!=0) s++;
else us++;
}
else
{
dfs(a);
if(color[b]==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
adnan2nd
New poster

Posts: 14
Joined: Sat Jul 03, 2004 1:18 pm
Location: bangladesh,ctg

### 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?
Please help!

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++)           dad[i] = 0;        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.
Ivo Sluganovic
New poster

Posts: 12
Joined: Tue Sep 21, 2004 10:08 pm

Hi !! Ivo Sluganovic try this Input
Input:
Code: Select all
`210c 1 5c 2 7q 7 1c 3 9q 9 6c 2 5q 7 510c 1 5c 2 7q 7 1c 3 9q 9 6c 2 5q 7 5`

Ouput:
Code: Select all
`1,21,2`

your output:
Code: Select all
`1,22,1`

Hope it helps
Keep posting !!

Ghust_omega
Experienced poster

Posts: 115
Joined: Tue Apr 06, 2004 7:04 pm
Location: Venezuela

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!
Ivo Sluganovic
New poster

Posts: 12
Joined: Tue Sep 21, 2004 10:08 pm

### 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
sql_lall
New poster

Posts: 2
Joined: Thu Sep 30, 2004 8:38 am
Location: Adelaide, Australia

PreviousNext

Return to Volume VII

### Who is online

Users browsing this forum: No registered users and 0 guests