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

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:

Post by sclo » Sat Feb 18, 2006 1:57 am

Yes, this can be done with topological sorting. First run dfs to topological sort the vertices.
assume now that the vertices are sorted in order such that vertex a can only depend on vertices a[j], where j<i.

Now we count the number of dependencies for vertex a.
Let C be that count:

Code: Select all

for i = 1 to n
   C[a[i]] = 0
   for j = 1 to i-1
      if i depends directly on j
         C[a[i]] = max( C[a[i]], C[a[j]] + 1)


User avatar
Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)

Post by Martin Macko » Mon Aug 07, 2006 9:42 am

Anonymous wrote:taking the example of

- A depends on B and C
- B depends on C
- D depends on C

how many dependencies are there for A?
2 or 3?

Thanks.
There are 2 dependencies for A (namely B and C) as nothing depends on D.

rhsumon
New poster
Posts: 48
Joined: Wed Aug 23, 2006 12:29 pm
Location: Dhaka

Post by rhsumon » Thu Nov 15, 2007 5:10 pm

I just call dfs_visit for all nodes .... i mean it is the right approach anyone plz check whar's my wrong.....

Code: Select all

int dfs_visit(int u){
	int i;
	col[u] = 1;
	for(i=1; i<=n; i++){
		if(!col[i] && mat[u][i]){
			count++;
			dfs_visit(i);
			col[i] = 1;
		}
	}
	col[u] = -1;
	return count;
}
Before all call i initial the value of color for all nodes......

AcmNightivy
New poster
Posts: 36
Joined: Tue Dec 04, 2007 10:20 am

Post by AcmNightivy » Wed Dec 05, 2007 2:12 pm

rhsumon wrote:I just call dfs_visit for all nodes .... i mean it is the right approach anyone plz check whar's my wrong.....

Code: Select all

int dfs_visit(int u){
	int i;
	col[u] = 1;
	for(i=1; i<=n; i++){
		if(!col[i] && mat[u][i]){
			count++;
			dfs_visit(i);
			col[i] = 1;
		}
	}
	col[u] = -1;
	return count;
}
Before all call i initial the value of color for all nodes......

Code: Select all

for(i=1; i<=n; i++){
		if(!col[i] && mat[u][i]){
			count++;
			dfs_visit(i);
			col[i] = 1;
		}
	}
i think the col = 1;should be del..for col has been visited and it needn't be visited again..maybe it will help

AcmNightivy
New poster
Posts: 36
Joined: Tue Dec 04, 2007 10:20 am

10926 - How Many Dependencies?

Post by AcmNightivy » Wed Dec 05, 2007 2:29 pm

I get AC in using DFS..so i modified the code in using BSF..but now i get RE..i have tested some cases and all of them work well..
here is my code:thanks a lot

Code: Select all

#include<iostream.h>
#include<stdlib.h>

#define MAX_NUM 101

void BFS(int Graph[][MAX_NUM],int n,int taskNum,bool visited[],int &tempMax,int queue[])
{
	int j;
	int * botton = queue;
	int * top = queue;
	int temp;

	visited[n] = true;
	for(j = 1;j <= Graph[n][0];j++)
	{
		*top++ = Graph[n][j];
		tempMax++;
		visited[Graph[n][j]] = true;
	}
	
	while(botton != top)
	{
		temp = *botton++;	//??
		for(j = 1;j <= Graph[temp][0];j++)
		{
			if(visited[Graph[temp][j]] == false)
			{
				*top++ = Graph[temp][j];
				tempMax++;
			}
		}
	}
}

int main()
{
	int Graph[MAX_NUM][MAX_NUM];
	int queue[100000];	//??
	int taskNum;
	int dependencyNum;
	int i,j;
	int maxTaskNum,identifier,tempMax;
	bool visited[MAX_NUM];			//?????????
	
	while(cin>>taskNum && taskNum != 0)
	{
		maxTaskNum = 0;				//??????
		identifier = 1;				//????1

		for(i = 1;i <= taskNum;i++)	//??task???
		{
			cin>>Graph[i][0];	//??task?????????????

			for(j = 1;j <= Graph[i][0] ;j++)
			{
				cin>>dependencyNum;
				Graph[i][j] = dependencyNum;
			}
		}

		for(i = 1;i <= taskNum;i++)	//????BFS
		{	
			tempMax = 0;	//??
			
			for(j = 1;j <= taskNum;j++)	//?????
			{
				visited[j] = false;
			}

			BFS(Graph,i,taskNum,visited,tempMax,queue);

			if(tempMax > maxTaskNum)	//??????
			{
				maxTaskNum = tempMax;
				identifier = i;
			}
		}
		cout<<identifier<<endl;
	}

	return 0;
}

AcmNightivy
New poster
Posts: 36
Joined: Tue Dec 04, 2007 10:20 am

Post by AcmNightivy » Sun Dec 09, 2007 7:16 am

help..

AcmNightivy
New poster
Posts: 36
Joined: Tue Dec 04, 2007 10:20 am

Post by AcmNightivy » Tue Dec 11, 2007 3:09 pm

it has puzzled me for 2 weeks...help!

User avatar
CMG
New poster
Posts: 37
Joined: Sat Dec 08, 2007 5:01 am
Location: ...

Post by CMG » Wed Dec 12, 2007 2:05 am

I couldnt find the runtime error with your code either, but you might want to fix your code since it does not give the right answer to this input:

Code: Select all

17
2 2 3
2 4 5
1 11
1 13
1 3
1 7
2 8 9
1 5
2 10 11
1 16
1 10
2 13 14
1 15
1 16
1 8
1 17
0
0
Your code outputs 6 as the max, but it should be 1.

AcmNightivy
New poster
Posts: 36
Joined: Tue Dec 04, 2007 10:20 am

Post by AcmNightivy » Wed Dec 12, 2007 2:44 pm

Thanks..your case help to find my mistake..
cause i did sign it as visited when i put it in the queue..So..
Thanks..Now it AC.~

qwerty
New poster
Posts: 21
Joined: Sun Feb 08, 2009 5:26 pm
Location: Mumbai,India

Re: 10926 - How Many Dependencies?

Post by qwerty » Fri Mar 05, 2010 9:05 am

prob fixed :D

Shafaet_du
Experienced poster
Posts: 147
Joined: Mon Jun 07, 2010 11:43 am
Location: University Of Dhaka,Bangladesh
Contact:

Re: 10926 - How Many Dependencies?

Post by Shafaet_du » Mon Oct 18, 2010 1:39 pm

Code: Select all

4
0
1 1
1 1
2 2 3
7
1 2
2 5 4
0
1 3
0
1 7
1 3
0
output:

Code: Select all

4
1

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

Re: 10926 - How Many Dependencies?

Post by a.elbashandy » Thu Mar 21, 2013 11:13 am

I've got WA and don't why .. please can anyone post some critical test cases ?

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 numPath[105];
int indegree[105];
vector<int> topoList;

void dfs(int x){
    visited[x] = true;
    for (int i = 0; i < adj[x].size(); i++) {
        if(!visited[adj[x][i]])
            dfs(adj[x][i]);
    }
    topoList.push_back(x);
}

int main(int argc, char** argv) {
    int n;
    while(scanf("%d", &n) && n){
        topoList.clear();
        for (int i = 0; i <= n; i++) {
            adj[i].clear();
            visited[i] = false;
            numPath[i] = 0;
            indegree[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[b].push_back(i);
                indegree[i]++;
            }
        }
        
        for (int i = 1; i <= n; i++) {
            if(!visited[i])
                dfs(i);
        }
        
        reverse(topoList.begin(), topoList.end());
                       
        for (int i = 0; i < topoList.size(); i++) {            
            if(!indegree[topoList[i]]){
                numPath[topoList[i]] = 1;
            }
        }

        numPath[topoList[0]] = 1;
        
        for (int i = 0; i < topoList.size(); i++) {
            int a = topoList[i];
            for (int j = 0; j < adj[a].size(); j++) {
                int b = adj[a][j];
                numPath[b] += numPath[a];
            }
        }
        
        int maxPath = 0; int indexOfMax = 0;
        for (int i = 1; i <= n; i++) {
            if(numPath[i] > maxPath){
                maxPath = numPath[i];
                indexOfMax = i;
            }
        }
        
        printf("%d\n", indexOfMax);
    }
    return 0;
}


AKJ88
New poster
Posts: 20
Joined: Wed Feb 13, 2013 10:48 am

Re: 10926 - How Many Dependencies?

Post by AKJ88 » Thu Mar 21, 2013 4:16 pm

I guess data set of this program isn't complete enough!!!;-)
I used a simple topological sort algorithm and although it wasn't giving the correct answer for some test cases I made it got AC :wink:
For example the correct answer for the following input should be 6 as it's produced by my other algorithm (using N times dfs as it was mentioned here in this forum) but my former method gives 4. :D
Can anyone give me an explanation?

Code: Select all

8
2 2 3
1 5
1 5
1 1
0
3 1 7 8
0
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 12:56 am

a.elbashandy, try running DFS N times.
AKJ88, yes wrong code can sometimes get AC.
Check input and AC output for thousands of problems on uDebug!

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 2:10 am

@brianfry713 thanks for the reply but i don't understand. do you mean removing the if condition " !visited " ?

Post Reply

Return to “Volume 109 (10900-10999)”