Page 7 of 9

Re: 459 - Graph Connectivity

Posted: Sat Sep 22, 2012 4:05 pm
by mahade hasan
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

Re: 459 - Graph Connectivity

Posted: Tue Sep 25, 2012 1:03 am
by brianfry713
http://www.cplusplus.com/reference/clib ... tdio/gets/
Your code was stuck in an infinite loop at EOF.

Re: 459 - WA

Posted: Fri Feb 08, 2013 9:42 pm
by prodhan
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.

Re: 459 - WA

Posted: Wed Feb 13, 2013 12:57 am
by brianfry713

Re: 459 - WA

Posted: Wed Feb 20, 2013 9:04 pm
by AKJ88
Hello.
Can anyone tell me what's wrong with my code?
Thanks.

Code: Select all

 Code was deleted after getting AC.

Re: 459 - WA

Posted: Wed Feb 20, 2013 11:18 pm
by brianfry713
From uhunt:
lbv> AKJ88, don't print a blank line after the last test case

Re: 459 - WA

Posted: Thu Feb 21, 2013 9:04 pm
by AKJ88
lbv & brianfry713, Thanks a lot.
Got AC.

Re: 459 - Graph Connectivity

Posted: Tue Aug 06, 2013 7:56 am
by fazel
i've tried every i/o i found in forums and got predicted answer :evil: :-?

but still it gives me Wrong answer

help me for god sake .....

Code: Select all

ACC god, al ham du llellah

Re: 459 - Graph Connectivity

Posted: Tue Aug 06, 2013 8:07 am
by fazel
ACC

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

Re: 459 - Graph Connectivity

Posted: Tue Sep 10, 2013 1:16 am
by brianfry713
Input:

Code: Select all

2

E
AB
CE
DB
EC

E
AB
CE
DB
EC

Re: 459 - Graph Connectivity

Posted: Wed Sep 11, 2013 1:07 am
by brianfry713
Input:

Code: Select all

1

A
AC output: 1

459 - Graph Connectivity - WA

Posted: Mon Sep 16, 2013 9:33 pm
by dumle
Why am I getting WA? Ive tried several inputs and cant find anything wrong.

Code: Select all

removed after ac

Re: 459 - Graph Connectivity - WA

Posted: Tue Sep 17, 2013 12:06 am
by brianfry713
Describe your algorithm.

Re: 459 - Graph Connectivity - WA

Posted: Tue Sep 17, 2013 10:04 pm
by dumle
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)

Re: 459 - Graph Connectivity - WA

Posted: Tue Sep 17, 2013 10:32 pm
by brianfry713
input:

Code: Select all

1

F
AB
CD
CE
CF
DE
DF
Output should be 2