793 - Network Connections

[Spider]

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.

[Faizur]

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

[wyanez]

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

[Riyad]

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
Riyad

[sohel]

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.

[Riyad]

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

[sohel]

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]

[Riyad]

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
Riyad

[Riyad]

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
Riyad

[miras]

look...

Multiple input....

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

and so on...

[adnan2nd]

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];
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')
{
if(m[a]==0) adj[a][++len[a]]=b;
if(m[a]==0) adj[++len]=a;
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");
}
}

[Ivo Sluganovic]

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

[Ghust_omega]

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

your output:

Code: Select all

1,2
2,1

Hope it helps
Keep posting !!

[Ivo Sluganovic]

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]

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.