OJ Board

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)

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

Code: Select all

for(i=1; i<=n; i++){
		if(!col[i] && mat[u][i]){
			count++;
			dfs_visit(i);
			col[i] = 1;
		}
	}

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

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

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

Code: Select all

4
1

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

Code: Select all

8
2 2 3
1 5
1 5
1 1
0
3 1 7 8
0
0