## 459 - Graph Connectivity

Moderator: Board moderators

saiful_sust
Learning poster
Posts: 97
Joined: Fri Aug 22, 2008 10:18 pm
Location: CSE.SUST.SYLHET

### Re: 459 - Graph Connectivity

I got ACC.........
taking input is the problem ...........
ugly input format.........

Igor9669
Learning poster
Posts: 85
Joined: Sun Jun 08, 2008 12:58 pm

### Re: 459 - Graph Connectivity

Input terminated by EOF!!!! Not by blank line! When I change it I got AC!

Obaida
A great helper
Posts: 380
Joined: Wed Jan 16, 2008 6:51 am

### Re: 459 - Graph Connectivity

Code: Select all

``removed...``
try_try_try_try_&&&_try@try.com
This may be the address of success.

New poster
Posts: 18
Joined: Sun Jan 24, 2010 11:17 am

### Re: 459 - Graph Connectivity

Thanks Igor9669 really ugly output format.Finally AC after 4 TLE & 1 WA

mustak
New poster
Posts: 8
Joined: Sun Sep 06, 2009 5:11 pm
Contact:

### Re: 459 - Graph Connectivity

My Code gets WA to the judge, I don't understand where is the problem. Please help me. Here is my code :

Code: Select all

``````#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

long p[30001];

long parent(long x)
{
if(p[x]==-1)
return x;
else{
p[x]=parent( p[x]);
return p[x];
}
}

int main()
{
long l,t,i,k,a[100],p1,p2,j,q,f;
char c[1000000],s[1000000];

cin>>t;
getchar();
getchar();

for(k=0;k<t;k++)
{
gets(c);
//getchar();

remove(c,c+strlen(c),' ');

for(i=0;i<=c[0]-'A';i++)
{
p[i]=-1;
a[i]=0;
}

while(gets(s))
{
if(s[0]=='\0')
break;
remove(s,s+strlen(s),' ');
p1=parent(s[0]-'A') ;
p2=parent(s[1]-'A') ;
if(p1!=p2)
p[p1]=p2;
}
l=0;f=0;
for(i=0;i<=c[0]-'A';i++)
{
q=parent(i);
for(j=0;j<l;j++)
{
if(a[j]==q)
{
f=1;
break;
}
}
if(f==0)
{
a[l]=q;
l++;
}
f=0;
}

cout<<l<<endl;
if(k!=t-1)
cout<<endl;
getchar();
}

return 0;
}
``````

helper
New poster
Posts: 1
Joined: Fri Feb 11, 2011 3:17 pm

### Re: 459 - Graph Connectivity

The input format for this problem is really very confusing ... i spend lot of time in this .. i am posting my way of taking input for someone's help

Code: Select all

``````#include<stdio.h>
#include<stdlib.h>

int parent[1000];
int node[150];
char s[100000];

void reset(int n);

int main(){

int i,j,k,test,count,n,res1,temp;
bool blank=false;
char dum,help[5],bfr[100];

scanf("%d%c",&test,&dum);
getchar();

while(test--){

do{
gets(bfr);
}while(!bfr[0]);

n=bfr[0];

reset(n);

while(gets(s)){

if(!s[0]) break;

temp=parent[s[1]];

}

}

return 0;

}
``````
hope it helps

SyFyKid
New poster
Posts: 26
Joined: Tue May 08, 2012 9:47 am

### Re: 459 - Graph Connectivity

realy crazy output
had to submit for 100500 time ... LAST line should be empty in your output.

I thought that the problem was in reading input... but its ok.
first you can read all input data except empty lines... after that - parse it and solve.

example from my code:

Code: Select all

``````ArrayList<String> input = new ArrayList<String>();
String line;

// input
while(true){
line = RLine();

if(line == null) break;
if(line.trim().isEmpty()) continue;

}
``````
and I finally got AC.

good luck!

Learning poster
Posts: 87
Joined: Thu Dec 15, 2011 3:08 pm

### Re: 459 - Graph Connectivity

cut>>
Last edited by mahade hasan on Sat Sep 22, 2012 4:08 pm, edited 1 time in total.
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

Find() looks slow.
Check input and AC output for thousands of problems on uDebug!

Learning poster
Posts: 87
Joined: Thu Dec 15, 2011 3:08 pm

### Re: 459 - Graph Connectivity

brianfry713 wrote:Find() looks slow.
Edited but still TLE.....
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

Post your updated code if you want.
Check input and AC output for thousands of problems on uDebug!

Learning poster
Posts: 87
Joined: Thu Dec 15, 2011 3:08 pm

### Re: 459 - Graph Connectivity

cut>>>>>>
Last edited by mahade hasan on Sat Sep 22, 2012 4:07 pm, edited 1 time in total.
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

Change line 24 to:
if(gets(Input)==NULL) break;
Check input and AC output for thousands of problems on uDebug!

Learning poster
Posts: 87
Joined: Thu Dec 15, 2011 3:08 pm

### Re: 459 - Graph Connectivity

brianfry713 wrote:Change line 24 to:
if(gets(Input)==NULL) break;
when i change this line got RE.............
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

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.
Check input and AC output for thousands of problems on uDebug!