## 459 - Graph Connectivity

Moderator: Board moderators

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

### Re: 459 - Graph Connectivity - WA

Ok, so my second for-loop was flawed since it only checked vectors right beside eachother.
Fixed it with a nested for-loop so it passed the test above, still WA tho :/

Code: Select all

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

I solved it using DFS.
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 - WA

Input:

Code: Select all

``````2

A

B``````
Output should be:

Code: Select all

``````1

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

Skynet094
New poster
Posts: 3
Joined: Fri Jul 19, 2013 6:31 pm

### Re: 459 - Graph Connectivity - WA

#include<cstdio>
#include<iostream>
#include<string>
#include<vector>
#include<cstring>
using namespace std;
#define MAX 500

int parent[MAX];

int find_r(int a);
void make_set(int N);
void Union(int a, int b);
int disjoint_count(int n);

void make_set(int N)
{
for(int i=1;i<=N;i++)
parent=i;
}

void Union(int a, int b)
{

int u=find_r(a);
int v=find_r(b);

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

}

}

int find_r(int a)
{
if(parent[a]==a)
return a;
else
{
return parent[a]=find_r(parent[a]);

}

}

int disjoint_count(int n)
{

int par[MAX];

int iter=0;
int flag;

for(int i=1;i<=n;i++)
{
flag=0;
int temp=find_r(i);

for(int j=iter+1;j>=1;j--)
if(par[j]==temp)
{
flag=1;
break;
}

if(flag==0)
{
par[++iter]=temp;

}

}

return iter;

}

int main(void)
{

int testcase;
cin>>testcase;
fflush(stdin);

int lol=testcase;
char ch;
string line;
vector<string>container;

while(testcase--)
{
memset(parent,0,sizeof(parent));

getline(cin,line);
cin>>ch;
fflush(stdin);

// cout<<ch<<endl;

make_set(ch-64);

getline(cin,line);
//cout<<line<<endl;

while(!line.empty())
{
container.push_back(line);
getline(cin,line);
}

for(int i=0;i<container.size();i++)
{
Union(container[0]-64,container[1]-64);
}

int _count=disjoint_count(ch-64);

cout<<_count<<endl;
if(testcase!=1)
cout<<"\n"<<endl;

}

return 0;
}
//Can someone tell me what to change, the code gives correct output in my compiler

shariftech
New poster
Posts: 1
Joined: Wed Nov 13, 2013 10:05 am

### Re: 459 - Graph Connectivity - TLE

Getting TLE ... I think it occurs because of ugly input ... But can not understand where is my fault ...

Code: Select all

``````#include<iostream>
#include<cstdio>
#include<cstring>
#include<cctype>
#define MAX 5000

using namespace std;
int par[1000];
int flag;
int node;
void makeset (int n)
{

for(int i=1; i<=n; i++)
par[i] = i;
}

int find (int a)
{

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

void makeunion(int a, int b)
{

int u = find(a);
int v = find(b);

if(u!=v){
par[u] = v;
}
}
int char2int (char c)
{

return c-'A'+1;
}

void input()
{

char ch[5];
while(gets(ch)&&ch[0]){

int ln;
ln = strlen(ch);
if(ln==1){
node = char2int(ch[0]);
makeset(node);
}
else{
int a = char2int(ch[0]);
int b = char2int(ch[1]);
makeunion(a,b);
}

}
}
void free ()
{
for(int i=0; i<=node; i++){
par[i]=0;
}
node = 0;
}

int main()
{
int n,i,j,a,b,cnt;

scanf("%d%*c%*c",&n);
flag = 0;

while(n--){
input();
cnt = 0;
for(i=1; i<=node; i++){
if(par[i]==i)
cnt++;
}
if(flag==0)
flag = 1;
else
cout<<endl;
cout<<cnt;
free();
}

return 0;
}
``````

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

### Re: 459 - Graph Connectivity - WA

Skynet094, don't use fflush(stdin);
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 - WA

shariftech, The outputs of two consecutive cases will be separated by a blank line. Always print a newline char at the end of the last line.
Check input and AC output for thousands of problems on uDebug!

walking_hell
New poster
Posts: 14
Joined: Tue Sep 24, 2013 4:35 pm

### uva 459

thanxxxxx....got accepted
Last edited by walking_hell on Thu Nov 21, 2013 5: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: uva 459

Try input:

Code: Select all

``````1

Z
AC
AE
AI
AL
AM
AN
AO
AQ
AS
AV
AW
AX
AY
BF
BH
BJ
BK
BL
BM
BN
BO
BP
BQ
BR
BU
BV
BW
BY
CE
CG
CI
CJ
CM
CP
CT
CU
CV
CY
DF
DG
DJ
DK
DL
DM
DN
DO
DQ
DV
DX
EF
EH
EK
EL
EM
EN
EO
ER
ES
ET
EU
EY
EZ
FG
FH
FI
FJ
FM
FN
FO
FP
FR
FU
FW
FY
FZ
GH
GL
GM
GP
GQ
GR
GS
GZ
HI
HJ
HK
HL
HQ
HR
HS
HV
HW
HY
IK
IM
IO
IP
IR
IU
IV
IX
IY
IZ
JK
JL
JM
JN
JR
JW
KM
KO
KP
KR
KS
KX
KY
KZ
LO
LP
LQ
LR
LY
MN
MO
MP
MR
MT
MU
MV
MX
MZ
NP
NR
NT
NV
NY
OQ
OV
OW
OX
PR
PS
PT
PV
PW
PX
PY
PZ
QR
QT
QV
QY
RT
RU
RW
RY
RZ
ST
SV
SZ
TX
TY
TZ
UW
UY
UZ
VW
WZ
XY
XZ
``````
Your code is throwing a seg fault
Check input and AC output for thousands of problems on uDebug!

shuvokr
Learning poster
Posts: 66
Joined: Tue Oct 02, 2012 8:16 pm

### Re: uva 459

@raihan.sust try this input:

Code: Select all

``````1

E
AB
``````

Code: Select all

``````so the graph is
A -> B
C
D
E``````
So what should be the result

Code: Select all

``enjoying life ..... ``

RookiE3
New poster
Posts: 16
Joined: Tue Feb 18, 2014 7:59 pm

### Re: uva 459

Please somebody help me with this code. I am getting TLE... It gives correct answers I think

Code: Select all

``````#include <bits/stdc++.h>
using namespace std;

int par[30];

void makeset(int n)
{
par[n] = n;
}

int findpar(int n)
{
if(par[n] == n)
return n;
else
return (par[n] = findpar(par[n]));
}

void Union(int a, int b)
{
int para = findpar(a);
int parb = findpar(b);

if(para != parb)
{
par[parb] = para;
}
}

int main()
{
freopen("in.txt", "r", stdin);

set<int> Sets;
int num, t;
char largest, a, b;

scanf("%d", &t);
getchar();
getchar();
while(t--)
{
Sets.clear();
num = 0;
scanf("%c", &largest);
if(largest == '\n')
break;
getchar();

for(char i='A'; i<=largest; i++)
makeset(i-64);

while(true)
{
a = getchar();
if(a != '\n')
b = getchar();
else
break;
Union(a-64, b-64);
getchar();
}
for(char i='A'; i<=largest; i++)
{
Sets.insert(findpar(i-64));
}
printf("%d\n\n", Sets.size());
}
return 0;
}

``````

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

### Re: uva 459

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

RookiE3
New poster
Posts: 16
Joined: Tue Feb 18, 2014 7:59 pm

### Re: uva 459

Please somebody help me. I am getting TLE in this problem...

Code: Select all

``````#include <bits/stdc++.h>
using namespace std;

int par[30];
int num;

void makeset(int n)
{
par[n] = n;
}

int findpar(int n)
{
if(par[n] == n)
return n;
else
return (par[n] = findpar(n));
}

void Union(int a, int b)
{
int para = findpar(a);
int parb = findpar(b);

if(para != parb)
{
par[parb] = para;
num++;
}
}

int main()
{
int t;
char largest;
char a, b;
scanf("%d", &t);
getchar();
while(t--)
{
num = 0;
scanf("%c", &largest);
getchar();
for(char i='A'; i<=largest; i++)
makeset(i-64);

while(true)
{
a = getchar();
if(a != '\n')
b = getchar();
else
break;
cout << a << " " << b;
Union(a-64, b-64);
getchar();
}

printf("%d\n", num);
}
return 0;
}
``````

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

### Re: uva 459

Try running your code on the sample input.
Check input and AC output for thousands of problems on uDebug!

mgavin2
New poster
Posts: 43
Joined: Sat Jul 28, 2012 6:29 pm

### Re: 459 - Graph Connectivity

I'm gonna throw my code up here because I'm not exactly sure what I'm doing wrong for this problem.
I'm new to trying to solve graph problems (that weren't implicit graphs modeled as ascii maps for like floodfill problems), so I'm trying to model this problem input as an adjacency matrix... and I think I'm traversing it right.

Thanks for your code review and insights that'll help me on other graph problems .

Code: Select all

``````AC

thank bfry :>
``````
Last edited by mgavin2 on Thu Oct 09, 2014 6:49 am, edited 1 time in total.
all that matters is AC