OJ Board

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

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

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
    }