久久综合噜噜激激的五月天,久久国产精品一区,久久se这里只有精品

UVa 10305

拓撲排序
雖然AC了，但還是覺得自己很不在狀態.

 1#include<stdio.h>
 2#include<string.h>
 3bool G[110][110];
 4int in[110], m, n;
 5struct stack{
 6    int q[110], t;
 7    stack() {memset(q, 0, sizeof(q)); t= 0;}
 8    void push(int x) {q[++t] = x;}
 9    int pop() {return q[t--];}
10    bool empty() {return t ? 0 : 1;}
11};
12void toposort(){
13    stack s;
14    int p[110], t = 0, i, j;
15    bool flag[110] = {0};
16    for (;;){
17        if (t == m) break;
18        for (i = 1; i <= m; i++)
19            if (!in[i] && !flag[i]) s.push(i);
20        while (!s.empty()){
21            i = s.pop();
22            p[++t] = i; 
23            flag[i] = 1;
24            for (j = 1; j <= m; j++)
25                if (G[i][j]) in[j]--;
26        }
27    }
28    for (i = 1; i < t; i++)
29        printf("%d ", p[i]);
30    printf("%d\n", p[t]);
31}
32int main(){
33    int i, x, y; 
34    while (scanf("%d%d", &m, &n) == 2 && (m || n)){
35        memset(G, 0, sizeof(G));
36        memset(in, 0, sizeof(in));
37        for (i = 1; i <= n; i++){
38            scanf("%d%d", &x, &y);
39            G[x][y] = 1;
40            in[y]++;
41        }
42        toposort();
43    }
44}
45

posted on 2010-09-23 21:43 Climber.pI 閱讀(293) 評論(0) 編輯收藏引用所屬分類: 圖論

只有注冊用戶登錄后才能發表評論。
【推薦】100%開源！大型工業跨平臺軟件C++源碼提供，建模，組態！



網站導航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

Climber.pI的OI之路

UVa 10305

導航

統計信息

News

常用鏈接

留言簿

隨筆分類

隨筆檔案

My Blog

搜索

最新評論

閱讀排行榜

評論排行榜