• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            付翔的專欄
            在鄙視中成長 記錄成長的點滴
            posts - 106,  comments - 32,  trackbacks - 0
            這次是自己仿寫的 圖的模板 而寫的拓撲排序

            和其他用矩陣的稍有不同

            //采用臨界表的形式 但是用數組來實現 其中要用C++ 的隊列stl 盡量使代碼的可用度提高
            // 網上大多采用 臨接矩陣的方式來做的
            # include<cstdio>
            # include
            <iostream>
            # include
            <queue>
            # include
            <vector>
            using namespace std;
            const int maxn = 510;
            struct graph
            {
                
            int edge[maxn][maxn];//edge[i][j] 表示第i個節點 第 j+1個邊 其值表示該邊的頂點
                int outdegree[maxn +1];//  頂點的出度
                int nvert ;//節點數
                int nedge;// 邊數  注意定點我們是從1 開始算 然后邊數我們是從0 開始的
            };
            typedef 
            struct graph GRAPH;

            struct graph g;// 圖的全局變量

            void init_graph()
            {
                
            int i;
                g.nedge 
            = 0;
                g.nvert 
            = 0;
                
            for (i = 1; i <=maxn ; i ++ ) g.outdegree[i] = 0;
            }
            void inert_graph(int x,int y,bool flag )
            {
                
            //if(g.outdegree[x] > maxn )//容錯
                g.edge[x][g.outdegree[x]] = y;
                g.outdegree[x] 
            ++;//出度 + 1
                if (flag == false)  inert_graph(y,x,true);//如果是無向圖 反向也要加
                else g.nedge ++;//邊數 ++

            }
            int read_graph(bool flag) //flag 用來控制 是否是有向圖
            {
                
            //這里可以根據實際情況添加代碼
                int n,i;
                
            int x,y;
                init_graph();
                
            if (scanf("%d%d",&g.nvert,&n)==EOF)
                    
            return 0;
                
            for (i =1; i <= n; i ++)
                {
                    scanf(
            "%d%d",&x,&y);
                    inert_graph(x,y,
            true);//是有向圖
                }
                
            return 1;
            }

            //拓撲排序  下面是top 排序所需要的東東
            int sorted[maxn];
            int indegree[maxn]; //計算入度
            int visted[maxn];
            void topsorted()
            {
                queue
            <int> zeroin;
                
            int x,y;
                
            int i,j;
                
            //初試化 入度數組
                for (i = 1; i <= maxn ; i ++)  indegree[i] = 0;
                
            //計算入度
                for (i = 1; i <= g.nvert ; i++ )
                    
            for (j = 0; j < g.outdegree[i]; j++// 所以這里我們是從 0 開始
                        indegree[g.edge[i][j]] ++;

                
            for(i = 1; i <= g.nvert ; i ++)
                {
                
            //for (i = g.nvert; i >= 1 ; i --)
                    if (indegree[i] == 0) zeroin.push(i);
                }
                j 
            = 0;
                memset(visted,
            0,sizeof(visted));
                
            for(j = 1;j <= g.nvert;j++)//  因為題目的原因 放棄隊列
                {
                    
            for(i = 1;i<=g.nvert;i++ )
                    {
                        
            if(visted[i] == 0 && indegree[i] == 0)
                        {
                            sorted[j] 
            = i,visted[i] = 1;
                            
            for(int k = 0;k< g.outdegree[i];k++)
                                indegree[g.edge[i][k]]
            --;
                            
            break;
                        }
                    }
                }

                
            //if(j != g.nvert) ;//表明只有 j個定點找到
            }

            void print_graph()
            {
                
            int i,j;
                
            for (i = 1; i <= g.nvert; i ++)
                {
                    printf(
            "%d: ",i);
                    
            for (j = 0; j < g.nvert ; j ++)
                        printf(
            " %d",g.edge[i][j]);
                    printf(
            "\n");
                }
            }
            int main()
            {
                freopen(
            "in.txt","r",stdin);

                
            while (read_graph(true)==1)
                {

                    topsorted();
                    
            //print_graph();
                    for (int i = 1; i <= g.nvert; i ++)
                        printf(i
            ==1?"%d":" %d",sorted[i]);
                    printf(
            "\n");
                }
                
            return 0;
            }



            posted on 2010-05-19 23:56 付翔 閱讀(1758) 評論(0)  編輯 收藏 引用 所屬分類: ACM 圖論

            <2012年7月>
            24252627282930
            1234567
            891011121314
            15161718192021
            22232425262728
            2930311234

            常用鏈接

            留言簿(2)

            隨筆分類

            隨筆檔案

            文章分類

            文章檔案

            CSDN - 我的blog地址

            博客

            搜索

            •  

            最新評論

            閱讀排行榜

            評論排行榜

            久久精品日日躁夜夜躁欧美| 久久精品国产精品亚洲毛片| 国产精品久久久久久久久| 精品熟女少妇a∨免费久久| 色偷偷888欧美精品久久久| 久久国产V一级毛多内射| 亚洲精品乱码久久久久久不卡| 精品少妇人妻av无码久久| 精品久久久无码人妻中文字幕| 国产真实乱对白精彩久久| 亚洲综合日韩久久成人AV| 久久精品国产99久久丝袜| 国产一级做a爰片久久毛片| 久久精品国产亚洲AV影院| 亚洲国产精品久久久久婷婷老年 | 女人香蕉久久**毛片精品| 人妻无码αv中文字幕久久琪琪布| 亚洲狠狠久久综合一区77777| 国产69精品久久久久777| 久久国产色AV免费看| 99久久精品国产一区二区蜜芽| 久久99国产精品久久99果冻传媒| 国产69精品久久久久9999| 午夜精品久久久久| 久久精品国产精品亚洲毛片| 99久久人妻无码精品系列| 久久亚洲电影| 亚洲中文久久精品无码ww16 | 久久99国产精品尤物| 亚洲午夜久久影院| 综合久久精品色| 伊人久久大香线蕉av不变影院| 久久99精品久久久久久动态图| 少妇无套内谢久久久久| 草草久久久无码国产专区| 亚洲国产精品久久久天堂| 久久综合丝袜日本网| 欧美午夜精品久久久久免费视| 理论片午午伦夜理片久久| 久久九九有精品国产23百花影院| 免费久久人人爽人人爽av|