10608 - Friends

All about problems in Volume 106. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
Location: Calgary, Canada

Representing graphs in Java 1.1

Post by Darko » 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

misof
A great helper
Posts: 430
Joined: Wed Jun 09, 2004 1:31 pm

Post by misof » 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 ;)

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
Location: Calgary, Canada

Post by Darko » 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

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
Location: Calgary, Canada

Post by Darko » 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

User avatar
Disatoba
New poster
Posts: 6
Joined: Thu Feb 02, 2006 3:32 pm
Location: Bogot

10608 - Friends

Post by Disatoba » 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.

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
Location: Calgary, Canada

Post by Darko » 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

User avatar
Disatoba
New poster
Posts: 6
Joined: Thu Feb 02, 2006 3:32 pm
Location: Bogot

WA or RTE?

Post by Disatoba » Sun May 07, 2006 6:46 pm

Hi Darko

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

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
Location: Calgary, Canada

Post by Darko » 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.

l314
New poster
Posts: 7
Joined: Sun Jan 28, 2007 9:53 am

I got WA.

Post by l314 » 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 !!!

ranban282
New poster
Posts: 37
Joined: Tue May 02, 2006 1:01 pm
Contact:

Why WA??

Post by ranban282 » 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?
Last edited by ranban282 on Sat Mar 03, 2007 11:55 am, edited 1 time in total.

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf » 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

1

100 7
1 2
2 3
3 4
5 6
6 7
7 8
4 6

ranban282
New poster
Posts: 37
Joined: Tue May 02, 2006 1:01 pm
Contact:

Post by ranban282 » Sat Mar 03, 2007 11:57 am

I got AC. Thanks very much for your help.

mogers
New poster
Posts: 29
Joined: Tue May 30, 2006 5:09 pm
Location: Porto, Portugal

Post by mogers » 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 ;)
Miguel Oliveira

rskvijay
New poster
Posts: 3
Joined: Fri Mar 23, 2007 5:57 pm

10608 -- WA plzz provide some test cases..

Post by rskvijay » 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

danielfukuciro
New poster
Posts: 1
Joined: Sat Nov 22, 2008 2:51 am

Re: 10608 - Friends

Post by danielfukuciro » 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

Post Reply

Return to “Volume 106 (10600-10699)”