10608 - Friends
Moderator: Board moderators
Representing graphs in Java 1.1
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
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
10608 - Friends
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.
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
![:(](./images/smilies/icon_frown.gif)
WA or RTE?
Hi Darko
Really thanks for the answer, for my program the message of the judge is:
Really thanks for the answer, for my program the message of the judge is:
I got WA.
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:
THANK YOU VERY MUCH !!!
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 !!!
Why WA??
I have absolutely no idea why this gives WA.
What is the point of solving problems when the problem statemant and sample I/O are contradictory?
Code: Select all
Cut After AC
Last edited by ranban282 on Sat Mar 03, 2007 11:55 am, edited 1 time in total.
Well, it doesn't work for instance on this test:I have absolutely no idea why this gives WA.
Code: Select all
1
100 7
1 2
2 3
3 4
5 6
6 7
7 8
4 6
10608 -- WA plzz provide some test cases..
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...
regards,
vijay
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
vijay
-
- New poster
- Posts: 1
- Joined: Sat Nov 22, 2008 2:51 am
Re: 10608 - Friends
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
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