## 10926 - How Many Dependencies?

Moderator: Board moderators

a.elbashandy
New poster
Posts: 12
Joined: Fri Dec 23, 2011 6:23 pm

### Re: 10926 - How Many Dependencies?

@brianfry713 I changed my algorithm to the one you suggested by running DFS N times and it's still WA and don't know why.

Code: Select all

``````#include <cstdlib>
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <cctype>
#include <stack>
#include <queue>
#include <list>
#include <vector>
#include <map>
#include <sstream>
#include <cmath>
#include <bitset>
#include <utility>
#include <set>
#include <numeric>

#define INF_MAX 2147483647
#define INF_MIN -2147483647
#define pi acos(-1.0)
#define N 1000000
#define LL long long

#define For(i, a, b) for( int i = (a); i < (b); i++ )
#define Fors(i, sz) for( size_t i = 0; i < sz.size (); i++ )
#define Fore(it, x) for(typeof (x.begin()) it = x.begin(); it != x.end (); it++)
#define Set(a, s) memset(a, s, sizeof (a))
#define Write(w) freopen(w, "w", stdout)

using namespace std;

struct node {
node(int node_x, int node_y, int node_t) : x(node_x), y(node_y), t(node_t) {}
int x, y, t;
};

bool visited[105];
int children[105];

void dfs(int src){
stack<int> s;
s.push(src);

while(!s.empty()){
int t = s.top();
s.pop();

visited[t] = true;
children[src]++;

for (int i = 0; i < adj[t].size(); i++) {
}

}
}

int main(int argc, char** argv) {
int n;
while(scanf("%d", &n) && n){
for (int i = 0; i <= n; i++) {
visited[i] = false;
children[i] = 0;
}

for (int i = 1; i <= n; i++) {
int a; scanf("%d", &a);
for (int j = 0; j < a; j++) {
int b; scanf("%d", &b);
}
}

for (int i = 1; i <= n; i++) {
Set(visited, false);
dfs(i);
}

int maxChildren = 0; int indexOfMax = 0;
for (int i = 1; i <= n; i++) {
if(children[i] > maxChildren){
maxChildren = children[i];
indexOfMax = i;
}
}

printf("%d\n", indexOfMax);
}
return 0;
}
``````

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 10926 - How Many Dependencies?

From uhunt:
AKJ88> @a.elbashandy Looks like you haven't read my post!!! change line 98 to: numPath = max(numPath, 1+numPath[a]); and you'll get it AC.
AKJ88> BTW what he meant was to start numPath for all vertices 0 then run DFS N times (reset visited to false for all) and ++ it for each vertex you visit. :::-(( Please read all posts!
Check input and AC output for thousands of problems on uDebug!

AnindyaPaul
New poster
Posts: 5
Joined: Sat Apr 06, 2013 12:42 pm
Contact:

### Re: 10926 - How Many Dependencies?

Here is an I/O for which I was getting WA.
Input:

Code: Select all

``````9
2 2 3
1 4
1 4
0
4 6 7 8 9
0
0
0
0
0
``````
Ouput:

Code: Select all

``5``

dexterhans
New poster
Posts: 1
Joined: Wed Feb 01, 2017 7:36 pm

### Re: 10926 - How Many Dependencies?

Code: Select all

``````import java.util.*;
@SuppressWarnings("serial")
{
}
private int V;
{
V=v;
for(int i=0;i<V;i++)
}
{
}
void topologicalSort(boolean[] visited,int v,HashSet<Integer> hs)
{
if(visited[v]==false)
visited[v]=true;
//int result=0;
while(list.hasNext())
{
int n=list.next();
if(visited[n]==false)
{
topologicalSort(visited,n,hs);
}
}

}

int maxDependency()
{
int[] count=new int[V];
int max=0,index=-1;
for(int i=0;i<V;i++)
{
boolean[] visited=new boolean[V];
HashSet<Integer> hs=new HashSet<Integer>();

topologicalSort(visited,i,hs);
count[i]=hs.size();
if(count[i]>max)
{
max=count[i];
index=i;
}
}
//	System.out.print("count array :");
//	for(int i=0;i<V;i++)
//		System.out.print(count[i]+" ");

return index+1;
}

}

class Dependencies{
public static void main(String[] args)
{
Scanner scan=new Scanner(System.in);
int scenario=scan.nextInt();
int dependNo,dependNode,i;
while(scenario!=0)
{
i=0;
while(i<scenario)
{
dependNo=scan.nextInt();
for(int j=1;j<=dependNo;j++)
{
dependNode=scan.nextInt();
}
i++;
}
/*		for(i=0;i<scenario;i++)
{
System.out.print(i +": ");
while(list.hasNext())
{
int n=list.next();
System.out.print(n+" ");
}
System.out.println();
}			*/