## 10926 - How Many Dependencies?

**Moderator:** Board moderators

- CodeMaker
- 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 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.

- Ghust_omega
- 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

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

- Ghust_omega
- 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

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.

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