10926 - How Many Dependencies?

[CodeMaker]

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?

[SRX]

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?

My algorithm is almost the same as you
do you initialize "gone array" after each node's dfs ?

[CodeMaker]

Got Accepted , there was a few mistakes in my code [ mixing up i,j ]

[sumankar]

1. There already are threads relating to this problem, check them out.
2. I used Floyd-Warshall, my favourite, though there are a host of other
possible alternatives. And it was slow. But it works

[Timo]

I only use DFS to get accepted from this problem.

[cypressx]

Timo , did you use the dfs for making a topological sort ? If yes , after this how did you count the value for every vertex ?

[Timo]

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.

[cypressx]

Thank you for your reply , I did it the same way .. but a friend told me that it could be done with topological sorting(if someone knows how it is done with top. sorting please tell) , this is why I asked you Anyway , thank you !

[Ghust_omega]

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

[daveon]

Hi,

I only considered verticies whos in-degrees are 0 but DFS does run through the whole graph.

[Ghust_omega]

Hi ! daveon

thanks for your pront answer

I consider the whole graph but I seek for the best of the values for all the vertices, I think that the best values are from the vertices that have in-degrre = 0 so this vertices are considered in my algo

thanks in advance
Keep posting

[daveon]

You're right, I only considered in-degree of 0 for an optimized solution.
Taking it out still gives me AC.

Hmmm, it would help me if you could explain your algorithm in more detail.

[Ghust_omega]

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,

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

[daveon]

Seems like even my corrections to your DFS gets WA.

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;
} 

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.

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
    } 

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.

[Ghust_omega]

Hi ! daevon

Thanks for your pront answer

Thanks !!!!!!!! gives me AC !! at last!!!!!!!!!!!! this problem make me mad because I didn't find the error, but with your algo I found, thanks again

Thanks in advance
Keep posting