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:
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)

Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)
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
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
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?

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];j++)
{
*top++ = Graph[n][j];
tempMax++;
visited[Graph[n][j]] = true;
}

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

int main()
{
int Graph[MAX_NUM][MAX_NUM];
int queue;	//??
int dependencyNum;
int i,j;
bool visited[MAX_NUM];			//?????????

{
maxTaskNum = 0;				//??????
identifier = 1;				//????1

{

for(j = 1;j <= Graph[i] ;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;
}

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

return 0;
}

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

AcmNightivy
New poster
Posts: 36
Joined: Tue Dec 04, 2007 10:20 am
it has puzzled me for 2 weeks...help!

CMG
New poster
Posts: 37
Joined: Sat Dec 08, 2007 5:01 am
Location: ...
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
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?

prob fixed 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?

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?

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;
};

bool visited;
int numPath;
int indegree;
vector<int> topoList;

void dfs(int x){
visited[x] = true;
for (int i = 0; i < adj[x].size(); 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++) {
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);
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] = 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?

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 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. 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?

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?

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