459 - Graph Connectivity

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

Moderator: Board moderators

Chow Wai Chung
New poster
Posts: 21
Joined: Sun Jan 19, 2003 4:01 pm
Location: Hong Kong

Post by Chow Wai Chung » Wed May 07, 2003 5:17 am

For an input with no edges, like this:

-------------------
1

B
-------------------

Should the output be the number of nodes (2 in this example)?
YES

User avatar
Angel
New poster
Posts: 8
Joined: Wed Nov 20, 2002 3:49 pm

Post by Angel » Wed Jul 23, 2003 12:33 am

this is my code .... I got wa first then after I included a blank line after the number of test case (this is a multiplr input problem right ?) ...I got tle ... I cant find whats wrong ,,what the tricky part here .....plzzzzz help me ...


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


void WeightedUnion(int i,int j);
int find(int i);

char N,dst,src,ch;
int r1,r2,prnt[30],temp,count=0;

void main(void)
{
int i,flag,o,n;
for(i=0;i<30;i++)prnt=-1;
while(scanf("%d",&n)==1)
{
ch=getchar();
ch=getchar();
for(o=0;o<n;o++)
{
scanf("%c",&N);
ch=getchar();
flag=0;
while(1)
{
scanf("%c",&src);
if(src!='\n')scanf("%c",&dst);
else break;
ch=getchar();
flag=1;
WeightedUnion(src-64,dst-64);
}
for(i=1;i<N-64;i++)
{
if(prnt<0)count++ ;
}
if(flag)printf("%d\n",count);
else printf("%d\n",N-64);

for(i=1;i<=N-64;i++)prnt=-1;
count=0;
}
}
}

void WeightedUnion(int i,int j)
{
r1=find(i);
r2=find(j);
if(r1!=r2)
{
temp=prnt[r1]+prnt[r2];
if(abs(prnt[r1])>=abs(prnt[r2]))
{
prnt[r2]=r1;
prnt[r1]=temp;
}
else
{
prnt[r1]=r2;
prnt[r2]=temp;
}
}
}


int find(int i)
{
while(prnt>0)
{
i=prnt;
}
return i;
}

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

problems with 459 problem

Post by miras » Thu Jul 24, 2003 11:06 am

hey!!!

i tried to solve 459 but i got WA :evil: why i tried with all of tests and i don't know what is wrong?
[pascal]
program p459;
const maxn=40;

var used:array[1..maxn] of boolean;
tab:array[1..maxn,0..maxn] of longint;
i,ii:char;
s:string;
il,qqq,q,wyn,ile,a,b,n:longint;




begin

READLN(IL);
FOR QQQ:=1 TO IL DO
BEGIN
readln;





for a:=1 to maxn do used[a]:=false;
for a:=1 to maxn do
begin
for b:=0 to maxn do
tab[a,b]:=0;
end;





readln(i);
ile:=ord(i)-64;

repeat
readln(s);
if s<>'' then
begin
i:=s[1];
ii:=s[2];
tab[ord(i)-64,ord(ii)-64]:=1;
inc(tab[ord(i)-64,0]);
tab[ord(ii)-64,ord(i)-64]:=1;
inc(tab[ord(ii)-64,0]);
end;

until (eof) or (eoln)or (s=' ');


used[1]:=true;

for a:=1 to ile do if tab[a,1]=1 then tab[a,1]:=-1;
n:=1; wyn:=1;

repeat
while used[n]=true do inc(n);
q:=0;
for a:=1 to ile do if tab[n,a]=-1 then begin a:=ile; q:=1; end;
if q=0 then inc(wyn);

used[n]:=true;


for a:=1 to ile do if tab[a,n]=1 then tab[a,n]:=-1;







until n=ile;




writeln(wyn);
writeln;
end;















end.




[/pascal]



thanx
__________________________
Made The Force Be With You :wink:

bobi1978
New poster
Posts: 13
Joined: Tue Jul 22, 2003 1:57 pm
Location: Kavadarci, Macedonia
Contact:

Post by bobi1978 » Fri Aug 01, 2003 12:20 pm

I had a lot of troubles with this problem. (especially with PASCAL).
Finally got ACCEPTED assuming INPUT as follows:

INPUT:
------------------------------
4
(blank)
F
AB
CF
(blank or eof)
C
AB
(blank or eof)
G
(blank or eof)
Z
AB
BC
XY
(blank or eof)
-------------------------

OUTPUT
--------------------------
4

2

7

23
-------------------------

I think this can help.

User avatar
mohiul alam prince
Experienced poster
Posts: 120
Joined: Sat Nov 01, 2003 6:16 am
Location: Dhaka (EWU)

459 TLE WHY

Post by mohiul alam prince » Wed Feb 25, 2004 3:19 pm

i have got TLE. but could not understand whats my problem.
this is a very easy problem.
in my code i have done

1.i have took input
2.and called my DFS function.

[cpp]
void dfs(long i)
{
long h;
for(h=1;h<=c1;h++)
if(A[h]==1 && vis[h]==0)
{
vis[h]=vis=1;
dfs(h);
}
}
[/cpp]
and my input format is very easy
can any body help me?[/cpp]

User avatar
malf
New poster
Posts: 7
Joined: Tue Aug 17, 2004 5:43 pm

Re: 459 TLE WHY

Post by malf » Sun Sep 05, 2004 5:08 pm

Can be at the time you get the input. Show me your source.

User avatar
malf
New poster
Posts: 7
Joined: Tue Aug 17, 2004 5:43 pm

459 - WA

Post by malf » Sun Sep 05, 2004 5:27 pm

I get WA all the time, I don't know why!!
:o :o :o :o

My source:

[c]
#include <stdio.h>


struct node;
typedef struct node {
char key; /* nodes are represented by a char */
int visited;
struct node *links[1000];
int numlinks;
} node;
node nodes[26];
int numnodes = 0;
/* lookup function. if no node is found for key, a new node is created */
node *lu(char key) {
int i;
for(i=0; i<numnodes; i++)
if(nodes.key == key) return &nodes;
nodes.key = key;
nodes.visited = 0;
nodes.numlinks = 0;
numnodes++;
return &nodes;
}
/* recusively visits nodes, marking them as visited */
void visit(node *n) {
if(!n->visited) {
int i;
n->visited = 1;
for(i=0; i<n->numlinks; i++)
visit(n->links);
}
}
int main() {
int i, graphs;
char line[4];
fgets(line, sizeof line, stdin);
for(i='A'; i<=line[0]; i++)
lu(i);
while(1) {
node *n1, *n2;
fgets(line, sizeof line, stdin);
if(line[0] == '\n') break;
n1 = lu(line[0]); n2 = lu(line[1]);
n1->links[n1->numlinks] = n2;
n1->numlinks++;
n2->links[n2->numlinks] = n1;
n2->numlinks++;
}
graphs = 0;
for(i=0; i<numnodes; i++){
if(!nodes.visited) {
graphs++;
visit(&nodes);
}
}
printf("%i\n", graphs);
return 0;
}[/c]

Minilek
Learning poster
Posts: 90
Joined: Tue Jul 27, 2004 9:34 am
Location: Cambridge, MA
Contact:

Post by Minilek » Mon Sep 06, 2004 4:34 pm

don't let the habit of always having < or >= in for loops mess you up too :)

[c]
AC
[/c]

[senu]
New poster
Posts: 6
Joined: Tue May 18, 2004 6:59 pm

Post by [senu] » Sun Sep 19, 2004 6:33 pm

grrrr...
can sbd paste here valid code [in c++] ?
i m interested only part with reading input.
thanks in advance

User avatar
Ghust_omega
Experienced poster
Posts: 115
Joined: Tue Apr 06, 2004 7:04 pm
Location: Venezuela

Post by Ghust_omega » Fri Oct 01, 2004 4:13 am

Hi malf did you solve this?? if not i can help you

Hope it helps
Keep posting!!

User avatar
A1
Experienced poster
Posts: 173
Joined: Wed Jan 28, 2004 3:34 pm
Location: Bangladesh

Post by A1 » Sat Oct 09, 2004 9:48 am

senu this is for you I take input using C function:

[c]
long Testcase,i,count;
char in[5];

scanf("%ld",&Testcase);

while(Testcase--)
{
scanf("%s",in);
max=in[0]-'@';
imat();
count=0;
gets(in);//for no use!!
while(gets(in)!=NULL)
{
if(in[0]=='\n'||in[0]=='\0')
break;
mat[in[0]-'@'][in[1]-'@']=1;
mat[in[1]-'@'][in[0]-'@']=1;
}
[/c]

Zuberul
New poster
Posts: 28
Joined: Sun Oct 24, 2004 9:46 pm
Location: dhaka
Contact:

Post by Zuberul » Mon Dec 20, 2004 5:39 am

I used disjoint set union-find data structure & got a WA.
help me with some I/O.

User avatar
Ghust_omega
Experienced poster
Posts: 115
Joined: Tue Apr 06, 2004 7:04 pm
Location: Venezuela

Post by Ghust_omega » Mon Dec 20, 2004 11:02 am

Hi !! Zuberul I used the same algo , but the input can be so tricky
In:

Code: Select all

3

E
   AB
CE
DB
EC

Z
   AB
CF

D       
                AB
CD     
ouput :

Code: Select all

2

24

2
Hope it helps
Keep posting !!

Zuberul
New poster
Posts: 28
Joined: Sun Oct 24, 2004 9:46 pm
Location: dhaka
Contact:

Post by Zuberul » Mon Dec 20, 2004 10:16 pm

Thanks a lot man.I got AC :D

User avatar
CodeMaker
Experienced poster
Posts: 183
Joined: Thu Nov 11, 2004 12:35 pm
Location: AIUB, Bangladesh

Post by CodeMaker » Thu Dec 23, 2004 5:22 am

:D Thanks omega for the I/O
Jalal : AIUB SPARKS

Post Reply

Return to “Volume 4 (400-499)”