题目：这里
题意：软件在安装之后需要重启才能发挥作用，现在给你一堆软件(有的需要重启有的不需要)以及安装这个软件之前需要哪些软件发挥作用，求最少的重启次数。
解法：真拓扑好题，但是我不会。然后这个题有两种解法，解法1来自斌神：普通的拓扑排序用了一个队列，而现在用两个队列q1，q2分别来存 不需要重启的software 和 需要重启的software。根据题目输入建好图后，按照拓扑序规则，首先将入度的0的点加进队列，当然不需要重启的进q1，需要的进q2。然后处理q1中的所有节点（即要删除这些点），那么要让与他们相连的节点的入度减1，如果发现减完入度为0，再判断其是否需要重启，并加进q1 or q2。一旦发现q1为空，那么使答案加1（即重启一次），把q2中所有元素加入q1，q2清空。如此循环直到q1，q2均为空即可。

//HDU 5098 topsort

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1020;
map <string, int> mp;
int cnt, edgecnt, reboot[maxn], out[maxn], in[maxn];
int head[maxn], vis[maxn];
struct edge{
    int v, nxt;
    edge(){}
    edge(int v, int nxt) : v(v), nxt(nxt) {}
}E[maxn*maxn];
void init(){
    edgecnt = cnt = 0;
    mp.clear();
    memset(head, -1, sizeof(head));
    memset(reboot, 0, sizeof(reboot));
    memset(out, 0, sizeof(out));
    memset(in, 0, sizeof(in));
}
void addedge(int u, int v){
    E[edgecnt].v = v, E[edgecnt].nxt = head[u], head[u] = edgecnt++;
}
int topsort(){
    queue <int> q1, q2;
    for(int i = 1; i <= cnt; i++){
        if(in[i] == 0){
            if(reboot[i] == 0) q1.push(i);
            else q2.push(i);
        }
    }
    int ans = 0;
    while(!q1.empty() || !q2.empty()){
        if(q1.empty() && !q2.empty()){
            ans++;
            while(!q2.empty()){
                q1.push(q2.front());
                q2.pop();
            }
        }
        while(!q1.empty()){
            int u = q1.front(); q1.pop();
            for(int i = head[u]; ~i; i = E[i].nxt){
                int v = E[i].v;
                in[v]--;
                if(in[v] == 0){
                    if(reboot[v] == 0) q1.push(v);
                    else q2.push(v);
                }
            }
        }
    }
    return ans;
}
int main()
{
    string s;
    char name[1010];
    int T, ks = 0;
    scanf("%d", &T);
    getchar();
    getchar();
    while(T--){
        init();
        printf("Case %d: ", ++ks);
        while(getline(cin, s)){
            if(s[0] == '\0') break;
            istringstream sin(s);
            sin >> name;
            int len = strlen(name);
            int flag = 0;
            if(name[len - 2] == '*'){
                flag = 1;
                name[len - 2] = '\0';
            }
            else{
                name[len - 1] = '\0';
            }
            string a, b;
            a = name;
            if(mp.find(a) == mp.end()) mp[a] = ++cnt;
            reboot[mp[a]] = flag;
            while(sin >> b){
                if(mp.find(b) == mp.end()) mp[b] = ++cnt;
                addedge(mp[b], mp[a]);
                out[mp[b]]++;
                in[mp[a]]++;
            }
        }
        int ans = topsort();
        printf("%d\n", ans);
    }
    return 0;
}

解法2来自hdu鸟神：建图同上，在建完的DAG图中求最长路，然后需要重启的点权为1，不需要的为0。这样找出最长路的权和即可。易证：只有具有从属关系的重启需要分别进行，不然可以同时搞掉。这样需要对每个入度为0的点求一次这样的最长路，取最大值即可，具体方法用DP可解。真orz。

//HDU 5098 topsort

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1020;
map <string, int> mp;
int cnt, edgecnt, reboot[maxn], out[maxn], in[maxn];
int head[maxn], vis[maxn], dp[maxn];
struct edge{
    int v, nxt;
    edge(){}
    edge(int v, int nxt) : v(v), nxt(nxt) {}
}E[maxn*maxn];
void init(){
    edgecnt = cnt = 0;
    mp.clear();
    memset(head, -1, sizeof(head));
    memset(reboot, 0, sizeof(reboot));
    memset(out, 0, sizeof(out));
    memset(in, 0, sizeof(in));
}
void addedge(int u, int v){
    E[edgecnt].v = v, E[edgecnt].nxt = head[u], head[u] = edgecnt++;
}

int dfs(int u){
    if(dp[u]) return dp[u];
    int ans = 0;
    for(int i = head[u]; ~i; i = E[i].nxt){
        int v = E[i].v;
        ans = max(ans, dfs(v));
    }
    return dp[u] = ans + reboot[u];
}

int DAGdp(){
    int ans = 0;
    memset(dp, 0, sizeof(dp));
    for(int i = 1; i <= cnt; i++){
        if(in[i] == 0){
            ans = max(ans, dfs(i));
        }
    }
    return ans;
}

int main()
{
    string s;
    char name[1010];
    int T, ks = 0;
    scanf("%d", &T);
    getchar();
    getchar();
    while(T--){
        init();
        printf("Case %d: ", ++ks);
        while(getline(cin, s)){
            if(s[0] == '\0') break;
            istringstream sin(s);
            sin >> name;
            int len = strlen(name);
            int flag = 0;
            if(name[len - 2] == '*'){
                flag = 1;
                name[len - 2] = '\0';
            }
            else{
                name[len - 1] = '\0';
            }
            string a, b;
            a = name;
            if(mp.find(a) == mp.end()) mp[a] = ++cnt;
            reboot[mp[a]] = flag;
            while(sin >> b){
                if(mp.find(b) == mp.end()) mp[b] = ++cnt;
                addedge(mp[b], mp[a]);
                out[mp[b]]++;
                in[mp[a]]++;
            }
        }
        int ans = DAGdp();
        printf("%d\n", ans);
    }
    return 0;
}