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

mahade hasan
Learning poster
Posts: 87
Joined: Thu Dec 15, 2011 3:08 pm
Location: University of Rajshahi,Bangladesh

### Re: 459 - Graph Connectivity

brianfry713 wrote:Post your updated code if you want. I took the code you posted most recently, changed the one line as I described, and got AC.
thanks man
its work but can u explain
why gets(Input);produce TLE
and if(gets(Input)==NULL) break;
is accepted
we r surrounded by happiness
need eyes to feel it!

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 459 - Graph Connectivity

http://www.cplusplus.com/reference/clib ... tdio/gets/
Your code was stuck in an infinite loop at EOF.
Check input and AC output for thousands of problems on uDebug!

prodhan
New poster
Posts: 2
Joined: Sat Oct 17, 2009 3:07 am

### Re: 459 - WA

I'm getting WA. can anybody help me pls?

Code: Select all

``````#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
#include<cstring>
using namespace std;

int par[30];

void make_set(int i)
{
par[i] = i;
}

int find(int r)
{

if(par[r]==r) return r;
else
{
return par[r] = find(par[r]);
}
}

void Union(int a, int b)
{
int u = find(a);
int v = find(b);

if(u==v) return;
else{
par[u] = v;
}
}

int main()
{

int T,u,v,max,i,j,temp,res;
char max_char;
char edge[3];

scanf("%d\n",&T);

while(T--){

while(1){
memset(edge,'\0',sizeof(edge));
gets(edge);
if(strlen(edge)==0) break;

if(strlen(edge)==1){
max_char = edge[0];

max = (int)max_char-64;
for(i=1; i<=max; i++)
make_set(i);
continue;

}

u = (int) edge[0] - 64;
v = (int) edge[1] - 64;
Union(u,v);

}
sort(par+1,par+1+max);

res = 0;

for(i=1; i<max; i++){
if(find(par[i])!=find(par[i+1]))
res++;
}

printf("%d\n",res+1);

if(T)
printf("\n");
}

return 0;
}
``````
Thanks in advance.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 459 - WA

Check input and AC output for thousands of problems on uDebug!

AKJ88
New poster
Posts: 20
Joined: Wed Feb 13, 2013 10:48 am

### Re: 459 - WA

Hello.
Can anyone tell me what's wrong with my code?
Thanks.

Code: Select all

`````` Code was deleted after getting AC.
``````
Last edited by AKJ88 on Thu Feb 21, 2013 9:05 pm, edited 1 time in total.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 459 - WA

From uhunt:
lbv> AKJ88, don't print a blank line after the last test case
Check input and AC output for thousands of problems on uDebug!

AKJ88
New poster
Posts: 20
Joined: Wed Feb 13, 2013 10:48 am

### Re: 459 - WA

lbv & brianfry713, Thanks a lot.
Got AC.

fazel
New poster
Posts: 6
Joined: Fri Aug 02, 2013 4:44 am

### Re: 459 - Graph Connectivity

i've tried every i/o i found in forums and got predicted answer

but still it gives me Wrong answer

help me for god sake .....

Code: Select all

``````ACC god, al ham du llellah
``````
Last edited by fazel on Mon Sep 09, 2013 3:26 pm, edited 1 time in total.

fazel
New poster
Posts: 6
Joined: Fri Aug 02, 2013 4:44 am

### Re: 459 - Graph Connectivity

ACC

F***er ,
after the last output must have one endl not more or less

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 459 - Graph Connectivity

Input:

Code: Select all

``````2

E
AB
CE
DB
EC

E
AB
CE
DB
EC``````
Check input and AC output for thousands of problems on uDebug!

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 459 - Graph Connectivity

Input:

Code: Select all

``````1

A
``````
AC output: 1
Check input and AC output for thousands of problems on uDebug!

dumle
New poster
Posts: 3
Joined: Mon Sep 16, 2013 9:23 pm

### 459 - Graph Connectivity - WA

Why am I getting WA? Ive tried several inputs and cant find anything wrong.

Code: Select all

``````removed after ac
``````
Last edited by dumle on Thu Sep 19, 2013 10:21 pm, edited 1 time in total.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 459 - Graph Connectivity - WA

Describe your algorithm.
Last edited by brianfry713 on Tue Sep 17, 2013 10:32 pm, edited 2 times in total.
Check input and AC output for thousands of problems on uDebug!

dumle
New poster
Posts: 3
Joined: Mon Sep 16, 2013 9:23 pm

### Re: 459 - Graph Connectivity - WA

Pretty much:

cin largest node letter, convert to int and insert into a vector

repeat until empty line:
{
getline and split the string into int a, int b
loop thru all vectors and check if a or b is in any vector
if: insert the missing one into the vector
if not: create a new vector with a and b (or only a if they're the same)

loop thru all vectors and check if you can find a or b in two vectors
if: join v and v[i+1] and remove duplicates. Remove v[i+1]
if not: do nothing
}

cout (largest node) - (sum of all vector sizes) + (number of vectors)

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 459 - Graph Connectivity - WA

input:

Code: Select all

``````1

F
AB
CD
CE
CF
DE
DF
``````
Output should be 2
Check input and AC output for thousands of problems on uDebug!