10608 - Friends

[Darko]

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 simple int[] to store the neighbors should be much faster. Don't use heavy artillery (e.g., hashtables) if it isn't necessary

[Darko]

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]

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

Darko

[Disatoba]

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]

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

[Disatoba]

Hi Darko

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

[Darko]

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]

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]

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?

[mf]

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]

I got AC. Thanks very much for your help.

[mogers]

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

[rskvijay]

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]

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