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

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

Re: 459 - Graph Connectivity

Post by saiful_sust » Mon Sep 07, 2009 10:52 pm

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

Post by Igor9669 » Wed Oct 28, 2009 3:00 pm

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
Location: (BUBT) Dhaka,Bagladesh.

Re: 459 - Graph Connectivity

Post by Obaida » Wed Nov 18, 2009 4:56 pm

Code: Select all

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

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

Re: 459 - Graph Connectivity

Post by Mehadi » Thu May 20, 2010 9:05 am

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

Post by mustak » Thu May 20, 2010 3:39 pm

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

Post by helper » Fri Feb 11, 2011 3:37 pm

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]];
						
		}

         //  Your  Algo  here.............

		
	}

	return 0;

}
hope it helps

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

Re: 459 - Graph Connectivity

Post by SyFyKid » Mon Jun 04, 2012 9:06 pm

realy crazy output :lol:
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;

            input.add(line.trim());
        }
and I finally got AC.

good luck!

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

Re: 459 - Graph Connectivity

Post by mahade hasan » Tue Aug 07, 2012 12:36 am

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

Post by brianfry713 » Tue Aug 07, 2012 11:53 pm

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

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

Re: 459 - Graph Connectivity

Post by mahade hasan » Wed Aug 08, 2012 6:15 pm

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 by brianfry713 » Wed Aug 08, 2012 9:00 pm

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

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

Re: 459 - Graph Connectivity

Post by mahade hasan » Wed Sep 12, 2012 8:28 pm

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

Post by brianfry713 » Thu Sep 13, 2012 9:52 pm

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

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

Re: 459 - Graph Connectivity

Post by mahade hasan » Sat Sep 15, 2012 4:14 pm

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 by brianfry713 » Sat Sep 22, 2012 12:23 am

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!

Post Reply

Return to “Volume 4 (400-499)”