10926 - How Many Dependencies?

[a.elbashandy]

@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 Read(r) freopen(r, "r", stdin)
#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; 
};

vector<int> adj[105];
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++) {
            if(!visited[adj[t][i]])
                s.push(adj[t][i]);
        }

    }
}

int main(int argc, char** argv) {
    int n;
    while(scanf("%d", &n) && n){
        for (int i = 0; i <= n; i++) {
            adj[i].clear();
            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);
                adj[i].push_back(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]

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!

[AnindyaPaul]

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]

Code: Select all

import java.util.*;
@SuppressWarnings("serial")
class Linkedlist extends LinkedList<Integer>
{
}
class AdjMatrix{
	private int V;
	private Linkedlist adj[];
	AdjMatrix(int v)
	{
		V=v;
		adj=new Linkedlist[V];
		for(int i=0;i<V;i++)
			adj[i]=new Linkedlist();
	}
	void addEdge(int x,int y)
	{
		adj[x].add(y);
	}
	void topologicalSort(boolean[] visited,int v,HashSet<Integer> hs)
	{
		if(visited[v]==false)
			visited[v]=true;
		Iterator<Integer> list=adj[v].listIterator();
		//int result=0;
		while(list.hasNext())
		{
			int n=list.next();
			if(visited[n]==false)
			{
				hs.add(n);
				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;
			AdjMatrix adjM=new AdjMatrix(scenario);
			while(i<scenario)
			{
				dependNo=scan.nextInt();
				for(int j=1;j<=dependNo;j++)
				{
					dependNode=scan.nextInt();
					adjM.addEdge(i,dependNode-1);
				}
				i++;
			}
	/*		for(i=0;i<scenario;i++)
			{
				System.out.print(i +": ");
				Iterator<Integer> list=adjM.adj[i].listIterator();
				while(list.hasNext())
				{
					int n=list.next();
					System.out.print(n+" ");
				}
				System.out.println();
			}			*/
			System.out.println(adjM.maxDependency());
			scenario=scan.nextInt();
		}
	}
}

i get runtime error in the following code though its satisfying the testcases. could anyone please look into it and let me know my mistake.