10926 - How Many Dependencies?

All about problems in Volume 109. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

User avatar
CodeMaker
Experienced poster
Posts: 183
Joined: Thu Nov 11, 2004 12:35 pm
Location: AIUB, Bangladesh

10926 - How Many Dependencies?

Post by CodeMaker » Sun Oct 02, 2005 5:58 pm

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? :(
Jalal : AIUB SPARKS

SRX
Learning poster
Posts: 63
Joined: Sat May 14, 2005 8:13 am
Location: Taiwan

Re: WA in 10926 [ how many dependencies ]

Post by SRX » Sun Oct 02, 2005 6:11 pm

CodeMaker 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? :(
My algorithm is almost the same as you
do you initialize "gone array" after each node's dfs ?

User avatar
CodeMaker
Experienced poster
Posts: 183
Joined: Thu Nov 11, 2004 12:35 pm
Location: AIUB, Bangladesh

Post by CodeMaker » Sun Oct 02, 2005 6:17 pm

Got Accepted :) , there was a few mistakes in my code :x [ mixing up i,j ]
Jalal : AIUB SPARKS

sumankar
A great helper
Posts: 286
Joined: Tue Mar 25, 2003 8:36 am
Location: calcutta
Contact:

Post by sumankar » Tue Oct 11, 2005 5:47 am

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
Learning poster
Posts: 70
Joined: Tue Oct 11, 2005 2:44 am
Location: Indonesia

Post by Timo » Fri Oct 14, 2005 4:10 am

I only use DFS to get accepted from this problem.

cypressx
New poster
Posts: 41
Joined: Sun Jul 04, 2004 12:16 pm

Post by cypressx » Mon Oct 17, 2005 12:53 am

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

Timo
Learning poster
Posts: 70
Joined: Tue Oct 11, 2005 2:44 am
Location: Indonesia

Post by Timo » Mon Oct 17, 2005 2:39 am

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.

:D

cypressx
New poster
Posts: 41
Joined: Sun Jul 04, 2004 12:16 pm

Post by cypressx » Mon Oct 17, 2005 11:53 am

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 !

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

10926 - How Many Dependencies?

Post by Ghust_omega » Wed Dec 28, 2005 2:34 am

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
Experienced poster
Posts: 229
Joined: Tue Aug 31, 2004 2:41 am
Location: TORONTO, CANADA

Post by daveon » Wed Dec 28, 2005 3:12 am

Hi,

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

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

Post by Ghust_omega » Thu Dec 29, 2005 1:41 am

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
Experienced poster
Posts: 229
Joined: Tue Aug 31, 2004 2:41 am
Location: TORONTO, CANADA

Post by daveon » Thu Dec 29, 2005 11:50 pm

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.

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

Post by Ghust_omega » Fri Dec 30, 2005 4:15 pm

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
Experienced poster
Posts: 229
Joined: Tue Aug 31, 2004 2:41 am
Location: TORONTO, CANADA

Post by daveon » Fri Dec 30, 2005 9:24 pm

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.

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

Post by Ghust_omega » Sat Dec 31, 2005 12:56 am

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

Post Reply

Return to “Volume 109 (10900-10999)”