## 459 - Graph Connectivity

Moderator: Board moderators

Chow Wai Chung
New poster
Posts: 21
Joined: Sun Jan 19, 2003 4:01 pm
Location: Hong Kong
For an input with no edges, like this:

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

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

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

Angel
New poster
Posts: 8
Joined: Wed Nov 20, 2002 3:49 pm
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

hey!!!

i tried to solve 459 but i got WA 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

FOR QQQ:=1 TO IL DO
BEGIN

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;

ile:=ord(i)-64;

repeat
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

bobi1978
New poster
Posts: 13
Joined: Tue Jul 22, 2003 1:57 pm
Contact:
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.

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

### 459 TLE WHY

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]

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

### Re: 459 TLE WHY

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

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

### 459 - WA

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

My source:

[c]
#include <stdio.h>

struct node;
typedef struct node {
char key; /* nodes are represented by a char */
int visited;
} 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;
numnodes++;
return &nodes;
}
/* recusively visits nodes, marking them as visited */
void visit(node *n) {
if(!n->visited) {
int i;
n->visited = 1;
}
}
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]);
}
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:
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
grrrr...
can sbd paste here valid code [in c++] ?
i m interested only part with reading input.

Ghust_omega
Experienced poster
Posts: 115
Joined: Tue Apr 06, 2004 7:04 pm
Location: Venezuela
Hi malf did you solve this?? if not i can help you

Hope it helps
Keep posting!!

A1
Experienced poster
Posts: 173
Joined: Wed Jan 28, 2004 3:34 pm
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:
I used disjoint set union-find data structure & got a WA.
help me with some I/O.

Ghust_omega
Experienced poster
Posts: 115
Joined: Tue Apr 06, 2004 7:04 pm
Location: Venezuela
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:
Thanks a lot man.I got AC

CodeMaker
Experienced poster
Posts: 183
Joined: Thu Nov 11, 2004 12:35 pm