拓扑排序:

两个队列,一个放不须要重新启动入度为0的,一个放须要重新启动入度为0的....从不须要重新启动的队列開始,每弹出一个数就更新下入度,遇到入读为0的就增加到对应队列里,当队列空时,记录重新启动次数+1,交换队列..一直到两个队列都为空

Smart Software Installer

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)

Total Submission(s): 78    Accepted Submission(s): 32

2

glibc:

gcc*: glibc

uefi*:

gcc*:

raid_util*: uefi

gpu_driver*: uefi

opencl_sdk: gpu_drivergcc

Case 1: 1

Case 2: 2 

#include <iostream>

#include <cstring>

#include <cstdio>

#include <algorithm>

#include <string>

#include <sstream>

#include <map>

#include <queue>

using namespace std;

const int maxn=2000;

map<string,int> mSI;

int nm;

bool restart[maxn];

int degree[maxn];

int hash(string name)

{

    int ret=mSI[name];

    if(ret==0)

    {

        mSI[name]=nm++;

        ret=nm-1;

    }

    return ret;

}

struct Edge

{

    int to,next;

}edge[maxn*maxn];

int Adj[maxn],Size;

void init()

{

    memset(Adj,-1,sizeof(Adj)); Size=0;

}

void add_edge(int u,int v)

{

    edge[Size].to=v; edge[Size].next=Adj[u]; Adj[u]=Size++;

}

int TUOPU()

{

    queue<int> q[2];

    int a=0,b=1;

    int n=nm-1;

    for(int i=1;i<=n;i++)

    {

        if(degree[i]==0)

        {

            if(restart[i]==true) q[b].push(i);

            else q[a].push(i);

        }

    }

    int time=0;

    while(!q[a].empty()||!q[b].empty())

    {

        while(!q[a].empty())

        {

            int u=q[a].front(); q[a].pop();

            for(int i=Adj[u];~i;i=edge[i].next)

            {

                int v=edge[i].to;

                degree[v]--;

                if(degree[v]==0)

                {

                    if(restart[v]==true) q[b].push(v);

                    else q[a].push(v);

                }

            }

        }

        if(q[b].empty()==true) continue;

        time++;swap(a,b);

    }

    return time;

}

int main()

{

    int T_T,cas=1;

    scanf("%d",&T_T);

    getchar(); getchar();

    while(T_T--)

    {

        init();

        mSI.clear(); nm=1;

        memset(restart,false,sizeof(restart));

        memset(degree,0,sizeof(degree));

        string line,name;

        while(getline(cin,line))

        {

            if(line[0]==0) break;

            istringstream sin(line);

            sin>>name;

            bool flag=false;

            int sz=name.size();

            if(name[sz-2]=='*')

            {

                flag=true;

                name[sz-2]=0;

                name.resize(sz-2);

            }

            else

            {

                name[sz-1]=0;

                name.resize(sz-1);

            }

            int to=hash(name);

            restart[to]=flag;

            while(sin>>name)

            {

                int from=hash(name);

                add_edge(from,to);

                degree[to]++;

            }

        }

        printf("Case %d: %d\n",cas++,TUOPU());

    }

    return 0;

}