題目描述 Description
Aiden陷入了一個奇怪的夢境：他被困在一個小房子中架谎，墻上有很多按鈕，還有一個屏幕，上面顯示了一些信息遮晚。屏幕上說，要將所有按鈕都按下才能出去迫悠，而又給出了一些信息鹏漆，說明了某個按鈕只能在另一個按鈕按下之后才能按下，而沒有被提及的按鈕則可以在任何時(shí)候按下创泄∫樟幔可是Aiden發(fā)現(xiàn)屏幕上所給信息似乎有矛盾，請你來幫忙判斷鞠抑。
輸入描述 Input Description
第一行饭聚，兩個數(shù)N，M搁拙，表示有編號為1...N這N個按鈕秒梳，屏幕上有M條信息。
接下來的M行箕速，每行兩個數(shù)ai酪碘，bi，表示bi按鈕要在ai之后按下盐茎。所給信息可能有重復(fù)兴垦，保證ai≠bi。（0＜N≤10000字柠，0<M≤2.5N）
輸出描述 Output Description
若按鈕能全部按下探越，則輸出“o(∩_∩)o”。
若不能窑业，第一行輸出“T_T”钦幔，第二行輸出因信息有矛盾而無法確認(rèn)按下順序的按鈕的個數(shù)。輸出不包括引號常柄。
Paste_Image.png
如果初學(xué)拓?fù)渑判蚶鹎猓@是一個很好的題，簡單的套一下模板就ok了西潘。
題目要求輸出無法確認(rèn)按下順序的按鈕個數(shù)铜异，其實(shí)就是：總點(diǎn)數(shù)n - 可以排序的點(diǎ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]) {//防止重復(fù)按下某一個按鈕
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]) {//因?yàn)橛兄剡? 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;
}
拓?fù)渑判蚴桥袛喹h(huán)的很好的方法秸架。拓展練習(xí)hdu1285, hdu3342, hdu2647揍庄。（tomorrow is another day ! ）
