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

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

Re: 10926 - How Many Dependencies?

Post by a.elbashandy » Fri Mar 22, 2013 4:13 pm

@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
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10926 - How Many Dependencies?

Post by brianfry713 » Fri Mar 22, 2013 9:33 pm

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
Location: Dhaka, Bangladesh
Contact:

Re: 10926 - How Many Dependencies?

Post by AnindyaPaul » Tue Nov 12, 2013 12:12 pm

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?

Post by dexterhans » Wed Feb 01, 2017 7:43 pm

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.

Post Reply

Return to “Volume 109 (10900-10999)”