10926  How Many Dependencies?
Moderator: Board moderators

 Experienced poster
 Posts: 183
 Joined: Thu Nov 11, 2004 12:35 pm
 Location: AIUB, Bangladesh
10926  How Many Dependencies?
Hi, will anyone plz explain this case:
1 > 2 > 4
and
1 > 3 > 4
then will I consider 1's count = 3 ( i mean, will '4' be counted once) ?
here is my algo, will anyone plz tell me why it fails.
I am using dfs and DAG. i select a starting node and visit all the nodes i can visit. (not visiting a node more than once). if the count is max, storing the node. then i start with another node refreshing the marking. did i miss something?
1 > 2 > 4
and
1 > 3 > 4
then will I consider 1's count = 3 ( i mean, will '4' be counted once) ?
here is my algo, will anyone plz tell me why it fails.
I am using dfs and DAG. i select a starting node and visit all the nodes i can visit. (not visiting a node more than once). if the count is max, storing the node. then i start with another node refreshing the marking. did i miss something?
Jalal : AIUB SPARKS
Re: WA in 10926 [ how many dependencies ]
My algorithm is almost the same as youCodeMaker wrote:Hi, will anyone plz explain this case:
1 > 2 > 4
and
1 > 3 > 4
then will I consider 1's count = 3 ( i mean, will '4' be counted once) ?
here is my algo, will anyone plz tell me why it fails.
I am using dfs and DAG. i select a starting node and visit all the nodes i can visit. (not visiting a node more than once). if the count is max, storing the node. then i start with another node refreshing the marking. did i miss something?
do you initialize "gone array" after each node's dfs ?
I am not use DFS to make topological sorting.
I only use DFS to count the value for every vertex.
So if there are N vertex my program will call N DFS Function to count the value for every vertex, but I am not count the same vertex twice. I mark every vertex that I used in my DFS function. After I count the value for all vertex then I find the maximum value.
I hope you understand with my explanation.
Sorry for my poor English.
I only use DFS to count the value for every vertex.
So if there are N vertex my program will call N DFS Function to count the value for every vertex, but I am not count the same vertex twice. I mark every vertex that I used in my DFS function. After I count the value for all vertex then I find the maximum value.
I hope you understand with my explanation.
Sorry for my poor English.

 Experienced poster
 Posts: 115
 Joined: Tue Apr 06, 2004 7:04 pm
 Location: Venezuela
10926  How Many Dependencies?
Hi !!!! to all
I stuck in this problem please help me
I use DFS to count the value for every vertex.
so I call DFS for every vertex, but I not count the same vertex twice.then I memorize every count for vertex that I used in DFS.
finally when I count the value for all vertex , I find the maximum value.
its all
if you have I/O or some hints please help me
if with this I/O i found my bug I will be very gratefull
Thanks in advance
keep posting
I stuck in this problem please help me
I use DFS to count the value for every vertex.
so I call DFS for every vertex, but I not count the same vertex twice.then I memorize every count for vertex that I used in DFS.
finally when I count the value for all vertex , I find the maximum value.
its all
if you have I/O or some hints please help me
if with this I/O i found my bug I will be very gratefull
Thanks in advance
keep posting

 Experienced poster
 Posts: 115
 Joined: Tue Apr 06, 2004 7:04 pm
 Location: Venezuela

 Experienced poster
 Posts: 115
 Joined: Tue Apr 06, 2004 7:04 pm
 Location: Venezuela
Hi ! daveon
thanks for your pront answer
here are a seudo code commented about mi algo I hope that you understead the algo is very simple just iniciliation of arrays and then do dfs,
Thanks in advance
Keep posting
thanks for your pront answer
here are a seudo code commented about mi algo I hope that you understead the algo is very simple just iniciliation of arrays and then do dfs,
Code: Select all
int Deps[102];
Graph graph;
int DFS(int v){
if(Deps[v] != 1)
return Deps[v];
int sum = 0;
// graph[v].size() give the size of list adyancencies for v
//graph[v][i] give the node adyacen to v that mean
// v > graph[v][i]
for(int i,i<graph[v].size()){
sum+=(1+DFS( graph[v][i] ));
}
Deps[v] = sum;
return sum;
}
int main(){
int n,a,b;
while(read(n)){
if(n==0)
break;
graph.clear();//clean the graph
read the graph
//fill de array Deps of Dependencies
for(int i=0;i<102;i++)//is 102 because its the size of array
Deps[i] = 1;
for(int i=1;i<=n;i++){
DFS(i);// Do DFS for all the vertices
}
int maxi = 1;//A max inicial
int res = 1;//the first node
for(int i=1,i<=n;i++){
if(maxi<Deps[i]){//Look the max in the array deps
maxi = Deps[i];
res = i;
}
}
print res;
}
return 0;
}
Thanks in advance
Keep posting
Seems like even my corrections to your DFS gets WA.
It seems alright to me but gets WA. My only other advice is to code it another way.
You may try a DFS that has 2 parameters.
These were one of those problems where I didn't even consider creating critical test cases.
Creating random IO takes a while because cyclic dependencies are not allowed.
Code: Select all
int DFS(int v){
if(Deps[v] != 1)
return Deps[v];
int sum = 0;
// graph[v].size() give the size of list adyancencies for v
//graph[v][i] give the node adyacen to v that mean
// v > graph[v][i]
// only DFS if not visited < CORRECTION
for(int i,i<graph[v].size()){
sum+=(1+DFS( graph[v][i] ));
}
Deps[v] = sum;
return sum;
}
You may try a DFS that has 2 parameters.
Code: Select all
void DFS(int base,int node)
{
int i;
if(base!=node) Deps[base]++;
visited[node]=true;
for(i=1;i<=N;i++)
if( (i adj to node) && (not visited[i]) )
DFS(base,i);
}
....
for(i=1;i<=N;i++){
// reset visited array to false
DFS(i,i);// Do DFS for all the vertices
}
Creating random IO takes a while because cyclic dependencies are not allowed.

 Experienced poster
 Posts: 115
 Joined: Tue Apr 06, 2004 7:04 pm
 Location: Venezuela