題目描述 Description

Aiden陷入了一個奇怪的夢境：他被困在一個小房子中，墻上有很多按鈕，還有一個屏幕，上面顯示了一些信息。屏幕上說，要將所有按鈕都按下才能出去，而又給出了一些信息，說明了某個按鈕只能在另一個按鈕按下之后才能按下，而沒有被提及的按鈕則可以在任何時候按下?？墒茿iden發(fā)現(xiàn)屏幕上所給信息似乎有矛盾，請你來幫忙判斷。

輸入描述 Input Description

第一行，兩個數(shù)N，M，表示有編號為1...N這N個按鈕，屏幕上有M條信息。
接下來的M行，每行兩個數(shù)ai，bi，表示bi按鈕要在ai之后按下。所給信息可能有重復，保證ai≠bi。（0＜N≤10000，0<M≤2.5N）

輸出描述 Output Description

若按鈕能全部按下，則輸出“o(∩_∩)o”。
若不能，第一行輸出“T_T”，第二行輸出因信息有矛盾而無法確認按下順序的按鈕的個數(shù)。輸出不包括引號。

Paste_Image.png

如果初學拓撲排序，這是一個很好的題，簡單的套一下模板就ok了。
題目要求輸出無法確認按下順序的按鈕個數(shù)，其實就是：總點數(shù)n - 可以排序的點的個數(shù)。

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

const int MAX_N = 1e4 + 5;
bool map[MAX_N][MAX_N];
bool vis[MAX_N];
int ind[MAX_N];//入度

int solve(int n) {
    priority_queue<int, vector<int>, greater<int> > q;
    for (int i = 1; i <= n; ++i) {
        if (!ind[i]) {
            q.push(i);
            vis[i] = true;
        }
    }
    int ans = 0;
    while (!q.empty()) {
        int s = q.top();
        --ind[s];
        q.pop();
        ++ans;
        for (int i = 1; i <= n; ++i) {
            if (map[s][i]) --ind[i];
            if (!ind[i] && !vis[i]) {//防止重復按下某一個按鈕
                q.push(i);
                vis[i] = true;
            }
        }
    }
    return ans;
}

int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < m; ++i) {
        int a, b;
        cin >> a >> b;
        if (!map[a][b]) {//因為有重邊
            map[a][b] = true;
            ++ind[b];
        }
    }
    int ans = n - solve(n);
    if (!ans) cout << "o(∩_∩)o" << endl;//ans=0表示每一個按鈕都按下了
    else cout << "T_T" << '\n' << ans << endl;
    return 0;
}

拓撲排序是判斷環(huán)的很好的方法。拓展練習hdu1285, hdu3342, hdu2647。（tomorrow is another day ! ）