793 - Network Connections

[rodriwan]

Hi, Im trying to send the folowing code, but I am geting wrong answear, I cant find where Im wrong... Im using quickfind algorithm, can anyone help?

[c]
"@BEGIN_OF_SOURCE_CODE"
/* @JUDGE_ID: xxxxxx 793 C */
#include <stdlib.h>
#include <stdio.h>
#include <ctype.h>

typedef unsigned long mytype;

int
main(int argc, char **argv)
{
char op;
mytype p, q, N;
mytype i, j;
mytype conected, unconected;
mytype *id;
char buff[500];

char getop(void);
void unionid(mytype *id, mytype p, mytype q, mytype N);
int find(mytype *id, mytype p, mytype q);

scanf("%ld", &N);

/* inicializa os vetores que conterao
* os logs da coneccao */
id = (mytype *) calloc(N+1, sizeof(mytype));
for (i = 1; i <= N; i++)
id[i] = i;

conected = unconected = 0;
while (fgets(buff, 500, stdin) != NULL) {
sscanf(buff, "%c %ld %ld", &op, &p, &q);
switch (op) {
case 'c': /* union */
if (!find(id, p, q))
unionid(id, p, q, N);
break;
case 'q': /* find */
if (find(id, p, q))
conected++;
else
unconected++;
break;
}
}
printf("%ld,%ld\n", conected, unconected);

return 0;
}

void unionid(mytype *id, mytype p, mytype q, mytype N)
{
mytype t, i;

for (t = id[p], i = 1; i <= N; i++)
if (id[i] == t)
id[i] = id[q];
}

int find(mytype *id, mytype p, mytype q)
{
return (id[p] == id[q]) ? 1 : 0;
}

"@END_OF_SOURCE_CODE"
[/c]

[Caesum]

this is a multiple input problem and you are not handling the input format correctly. read the notes on the format for multiple input (see the blue tick by the name of the problem ?). when thats fixed it will be accepted.

[htl]

I check my code again and again. But it still got RE. I think the number of computers won't be bigger than 10000. Where are the bugs?
[c]
#include<stdio.h>
#include<string.h>
void unionfunc(int,int);
int find(int);
int parent[10000];
void main(void)
{
int count,x,i,j,n,y,yes,no,temp,rooti,rootj;
char c,buffer[50];
scanf("%d",&count);
for(x=0;x<count;x++)
{
if(x!=0)
printf("\n");
scanf("%d\n",&n);
for(y=0;y<n;y++)
parent[y]=-1;
yes=no=0;
while(1)
{
if(fgets(buffer,50,stdin)==NULL)
break;
buffer[strlen(buffer)-1]='\0';
if(!strlen(buffer))
break;
for(y=0;buffer[y]!='\0';y++)
if(buffer[y]>='0' && buffer[y]<='9')
break;
for(i=0;buffer[y]!=' ';y++)
i=i*10+buffer[y]-'0';
for(;buffer[y]!='\0';y++)
if(buffer[y]>='0' && buffer[y]<='9')
break;
for(j=0;buffer[y]!='\0';y++)
j=j*10+buffer[y]-'0';
if(buffer[0]=='c')
{
rooti=find(i-1);
rootj=find(j-1);
unionfunc(rooti,rootj);
}
else
{
rooti=find(i-1);
rootj=find(j-1);
if(rooti==rootj)
yes++;
else
no++;
}
}
printf("%d,%d\n",yes,no);
}
}
void unionfunc(int i,int j)
{
int temp;
temp=parent[i]+parent[j];
if(parent[i]>parent[j])
{
parent[i]=j;
parent[j]=temp;
}
else
{
parent[j]=i;
parent[i]=temp;
}
}
int find(int i)
{
int root,trail,lead;
for(root=i;;)
if(parent[root]>=0)
root=parent[root];
else
break;
for(trail=i;;)
if(trail!=root)
{
lead=parent[trail];
parent[trail]=root;
trail=lead;
}
else
break;
return root;
}
[/c]

[htl]

Could someone help me with the code? I really want to know if my code of find&union algo is correct.

[obayashi]

i use disjoint tree(Union() and Find()) to solve this problem but unfortunately i kept getting TLE
any one could be any of help?

here's the code
[cpp]
#include <iostream>
#include <string.h>
#include <stdlib.h>
#define myin cin
using namespace std;
int parent[1000],root[1000];
inline int Find (int e) {
int j = e, f = e, pf;
while (!root[j])
j = parent[j];
while (f!=j) {
pf = parent[f];
parent[f] = j;
f = pf;
}
return j;
}
inline void Union (int i,int j) {
int ri,rj;
ri = Find(i);
rj = Find(j);
parent[rj] = ri;
root[rj] = 0;
}
int main () {
int i,j,cas,n,s,t,con,discon;
char c,tmp[100],*p;
myin>>cas;
myin.getline(tmp,1);
myin.getline(tmp,1);
for (i=0;i<cas;i++) {
if (i>0)
cout<<endl;
myin>>n;
myin.getline(tmp,1);
for (j=0;j<=n;j++) {
parent[j] = 0;
root[j] = 1;
}
con = discon = 0;
while (1) {
myin.getline(tmp,99);
if (*tmp=='\0')
break;
p = strtok(tmp," \t\b\r\n");
c = *p;
p = strtok(NULL," \t\b\r\n");
s = atoi(p);
p = strtok(NULL," \t\b\r\n");
t = atoi(p);
if (c=='c') {
Union(s,t);
} else {
if (Find(s)==Find(t))
con++;
else
discon++;
}
}
cout<<con<<","<<discon<<endl;
}
return 0;
}

[/cpp]

[liusu]

i try again and again,but still WA.......
please help.
thank you very much!!!!!!!!

[pascal]var
s:array[1..1000] of integer;
bool:array[1..1000] of boolean; //judge if it was connected
total:integer;

procedure inis(total:integer);
var
i:integer;
begin
for i:=1 to total do
begin
s[i]:=i;
bool[i]:=false;
end;
end;

procedure done;
var
su,un,i,total,m,n,tem:integer;
ch:char;
begin
su:=0;
un:=0;
readln(total);
inis(total);
read(ch);
while(ch='q')or(ch='c') do
begin
readln(m,n);
if(ch='c') then
begin
if (not bool[m])and(not bool[n]) then
begin
s[m]:=n;
bool[m]:=true;
bool[n]:=true;
end
else if(not bool[m]) then
begin
bool[m]:=true;
s[m]:=s[n];
end
else if(not bool[n]) then
begin
bool[n]:=true;
s[n]:=s[m];
end
else begin
if(s[m]<>s[n]) then
begin
tem:=s[m];
for i:=1 to total do
if s[i]=tem then
s[i]:=s[n];
end;
end;
end
else if(ch='q') then
begin
if(s[m]=s[n]) then inc(su)
else inc(un);
end;
read(ch);
end;
writeln(su,',',un);
// for i:=1 to total do
// writeln(i,' ',s[i]);
writeln;
end;

begin
readln(total);
while (total>0) do
begin
done;
dec(total);
end;
end.[/pascal]

[liusu]

NO one can help me?What a pity..

[zsacul]

I have no more ideas what is wrong...
Alghoritm is simple union-find...
Can you help me?

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

int nr[2000];
unsigned long n;

void unionID(int what,int newID)
{
for (unsigned long i=0;i<n;i++)
{
if (nr[i]==what) nr[i] = newID;
}
}

bool question(unsigned long n1,unsigned long n2)
{
if (nr[n1-1]==nr[n2-1]) return true;
else return false;
}

int main(int argc, char **argv)
{
int mm;
scanf("%d\n",&mm);

for (int prob=0;prob<mm;prob++)
{
if (prob>0) printf("\n");
unsigned long n1,n2,i;
unsigned long odpCon = 0;
unsigned long odpNot = 0;
char c;

scanf("%d\n",&n);
assert(n<2000);

for (i=0;i<n;i++) nr[i]=i;
scanf("%c %ld %ld\n",&c,&n1,&n2);

while ((c=='c')||(c=='q'))
{
assert( (c=='c')||(c=='q') );

if (c=='c')
{
if (!question(n1,n2)) unionID(nr[n1-1],nr[n2-1]);
}

if (c=='q')
{
if (question(n1,n2)) odpCon++;
else odpNot++;
}
c = 0;
scanf("%c %ld %ld\n",&c,&n1,&n2);
}

printf("%ld,%ld\n",odpCon,odpNot);
}

return 0;
}
[/cpp]

[Picard]

the input reading has an error. after the last 'c'/'q' line you read into the next input block because scanf("\n") reads more newline chars (and the next "scanf("%d\n",&n);" will fail).
i used (instead of the two scanf("%c ...)
[cpp]char s[256];
while (gets(s) && sscanf(s," %c %d %d",&c,&n1,&n2)==3)[/cpp]

[zsacul]

Thank you, I've got accepted!

[yahoo]

I can't understand how i can take input in this problem. I have tried with scanf but it seems not to work. Please help me.

[ec3_limz]

Hi,

This type of problems are pretty irritating when it comes to input.

Here's how to do the input. Input the test case line by line into a string, and use a "string reader" to read the input from the string.

If you are using C (like me), you use the function gets(str) to input the line into a string str, and then you use the function sscanf(str, ...), to read input from str.

If you are using standard C++ classes, use the cin.getline() function to read in the line, and use the istrstream stream (found in <strstream>) to read input from a line.

To detect an end in the test case, simply test for (feof(stdin) || strlen(str)==0) if you're using C, or (cin.eof() || str.length()==0) if you're using standard C++ classes.

Hope this helps.

[Angel]

what is the input terminating condition ??
I considered it as a blank line....
but Got WA .... Whats wrong here .....plz help me ....
here's my code....

#include<stdio.h>
#include<string.h>

void input();
void search();

int N,i,src,dst,G[100][100],yes,no,flag;
char ch,ins,A[6];


void main(void)
{


scanf("%d\n",&N);
{
yes=0;no=0;

while(gets(A))
{
if(A[0]!='q'&&A[0]!='c')break;
src=A[2]-48;
dst=A[4]-48;
if(A[0]=='c')input();
else search();
}
printf("%d,%d\n",yes,no);
}
}


void input()
{
G[src][dst]=1;
G[dst][src]=1;
}

void search()
{
flag=0;
if(G[src][dst]==1)yes++;
else
{
for(i=1;i<=N;i++)
{
if(G[src][i])
{
if(G[i][dst])
{
flag=1;
yes++;
}
else
{
flag=1;
no++;
}
}

}
if(flag!=1)no++;
}
}

[shamim]

The total number of test case is as indicated by N, the last set ends at EOF and not a newline.

[Angel]

I consider EOF .... while(gets(A))... wont it break at EOF ????
if not ... then how would I consider it .. ???
I test my program with freopen ... for the sample out put (without blank line...it means the loop is breaking at the EOF...is it ??? )