OJ Board

Posted: **Thu Feb 23, 2006 6:57 pm**

Hi,

I've been trying a problem (10608 Friends) that needs an adjacency list representation of a graph, but my implementation is too slow.

My nodes are Strings and the graph is a Hashtable of (String, Vector) pairs where Vector contains neighbours of the node.

While doing DFS, I put visited nodes in another Vector. It seems that checking if a node is in there is really expensive (visited.contains(node)).

Is there a better way to do it? Well, obviously there is, because people have AC in that problem in Java, but I really don't know how to speed this thing up.

For that particular problem, it takes me 2.2 secs just to build graph and go through all of the nodes. Doing DFS gives me TLE.

Darko

Posted: **Thu Feb 23, 2006 7:33 pm**

A simple int[] to store the neighbors should be much faster. Don't use heavy artillery (e.g., hashtables) if it isn't necessary

Posted: **Thu Feb 23, 2006 7:52 pm**

Hm, never thought about reading everything in and then building a graph after I knew something about it. I just did a "straight-forward" thing.

Thanks misof

Darko

Posted: **Fri Mar 03, 2006 1:52 am**

Never mind that, there is no need to build a graph in that problem at all. I am learning new stuff every day

Darko

Posted: **Sun May 07, 2006 5:42 am**

I got WA in 10608 friends problem, help.

I had solved friends problem in Java language, but i got WA , i dont know why WA, if you should help me with any test cases, i would be thankful to you

thanks.

Posted: **Sun May 07, 2006 10:03 am**

If you got WA in Java, it is not necessarily WA. How long did it take to get WA? If it is something short, it might be a Run Time Error. Check the time against those C solutions, if your WA is faster (or among fastest), it is definitely RTE.

Darko

Posted: **Sun May 07, 2006 6:46 pm**

Hi Darko

Really thanks for the answer, for my program the message of the judge is:

Posted: **Sun May 07, 2006 6:55 pm**

I don't know, the only thing I can think of (if you are convinced that your program should work) is that the last line of the input doesn't have a newline at the end and you are expecting one? Your time sounds reasonable, so if it crashes, it probably crashes there.

Posted: **Wed Feb 28, 2007 3:07 pm**

I'm getting W.A. Don't Know why .

I tested the program with a lot of inputs, and the answers were correct.

I will really appreciate some test cases...

I'm also posting my code:

Code: Select all

#include <iostream>
#include <stdio.h>

using namespace std;

int Find_Set(int);
void Link(int,int);
void Union(int,int);

const int MAX_N = 30001;

int p[MAX_N], rank[MAX_N], number[MAX_N];

int main()
{
  int num,n,m,node1,node2,max=0;  
  cin>>num;
  while(num--)
  {
    scanf("%d %d",&n,&m);
    for(int i=0; i<n; i++){
       p[i]=i;
       rank[i]=0;
       number[i]=1;
    }
    
    while(m--)
    {
      scanf("%d %d", &node1, &node2);
      Union(node1,node2);
    }
    
    for(int i=0; i<n; i++)
    {  
       max = max > number[i]? max : number[i];        
    }
    cout<<max<<endl;
  }
}

int Find_Set(int x)
{
   if(x != p[x])
      p[x] = Find_Set(p[x]);
   return p[x];   
}

void Link(int x, int y)
{ 
  if( x == y)
    return;
       
  if(rank[x] > rank[y]){
    p[y] = x;
    number[x]+= number[y];
  }  
  else{
    p[x] = y;
    number[y] += number[x];
    if(rank[x] == rank[y])
       rank[y]++; 
  }           
}

void Union(int x, int y)
{ 
   Link(Find_Set(x),Find_Set(y));
}

THANK YOU VERY MUCH !!!

Posted: **Fri Mar 02, 2007 6:22 pm**

I have absolutely no idea why this gives WA.

Code: Select all

Cut After AC

What is the point of solving problems when the problem statemant and sample I/O are contradictory?

Posted: **Fri Mar 02, 2007 6:49 pm**

I have absolutely no idea why this gives WA.

Well, it doesn't work for instance on this test:

Code: Select all

Posted: **Sat Mar 03, 2007 11:57 am**

I got AC. Thanks very much for your help.

Posted: **Wed Apr 04, 2007 10:21 pm**

well, probably you have already solved it. it has been over a month from your post : x

your problem is simple:
you should initialize max = 0 for every input

Posted: **Sun Mar 23, 2008 5:22 am**

Hi guyz,

here is my code for 10608 friends problem... i am getting WA everytime, i tried a few test cases and got the expected output.. plzz figure out the bug or provide me some inputs so that i can figure it out...

Code: Select all


 sorry... that was a silly mistake ... removed after getting AC

regards,
vijay

Posted: **Sat Nov 22, 2008 2:56 am**

l314, I think I know what is your problem.
You initialization your set in range [1, n-1].
Then scanf(" %d %d", &u, &v);
When you do an unite_set(v, u), you have to do unit_set(u-1, v-1), because in the input will have numbers like 10, and you just did:

for (int i = 0; i < n; i++) { //[0, 9]
rank = 0;
number = 1;
p = i;
}

Understood? Cya

OJ Board

10608 - Friends

Representing graphs in Java 1.1

10608 - Friends

WA or RTE?

I got WA.

Why WA??

10608 -- WA plzz provide some test cases..

Re: 10608 - Friends