• <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>

            superman

            聚精會神搞建設(shè) 一心一意謀發(fā)展
            posts - 190, comments - 17, trackbacks - 0, articles - 0
               :: 首頁 :: 新隨筆 :: 聯(lián)系 :: 聚合  :: 管理

            ZOJ 1060 - Sorting It All Out

            Posted on 2008-04-03 18:16 superman 閱讀(340) 評論(0)  編輯 收藏 引用 所屬分類: ZOJ
              1 /* Accepted 1060 C++ 00:00.06 848K */
              2 #include <string>
              3 #include <iostream>
              4 
              5 using namespace std;
              6 
              7 class Graph
              8 {
              9 private:
             10     int n, e;
             11     int count[26];
             12     bool map[26][26];
             13 public:
             14     Graph(const int nn)
             15     {
             16         n = nn; e = 0;
             17         memset(count, 0sizeof(count));
             18         memset(map, falsesizeof(map));
             19     }
             20     void AddEdge(const int s, const int t)
             21     {
             22         e++;
             23         if(map[s][t] == false)
             24             count[t]++;
             25         map[s][t] = true;
             26     }
             27     bool TopSort(int x[])
             28     {
             29         int cn = n;
             30         int cnt[26];
             31         memcpy(cnt, count, sizeof(count));
             32         
             33         while(cn--)
             34         {
             35             int tot = 0, index;
             36             for(int i = 0; i < n; i++)
             37                 if(cnt[i] == 0)
             38                 {
             39                     index = i;
             40                     tot++;
             41                 }
             42             if(tot > 1)
             43                 return 0;
             44             if(tot == 1)
             45             {
             46                 for(int i = 0; i < n; i++)
             47                     if(map[index][i])
             48                         cnt[i]--;
             49                 x[cn] = index;
             50                 cnt[index] = -1;
             51             }
             52         }
             53         return 1;
             54     }
             55     bool ExistCycle()
             56     {
             57         bool f[26][26];
             58         memcpy(f, map, sizeof(map));
             59         for(int k = 0; k < n; k++)
             60         for(int i = 0; i < n; i++)
             61         for(int j = 0; j < n; j++)
             62             if(f[i][k] && f[k][j])
             63                 f[i][j] = 1;
             64         for(int i = 0; i < n; i++)
             65             if(f[i][i])
             66                 return 1;
             67         return 0;
             68     }
             69 };
             70 
             71 int main()
             72 {
             73     int n, m;
             74     string relation;
             75     while((cin >> n >> m) && n && m)
             76     {
             77         Graph G(n);
             78         bool find = false;
             79         for(int i = 1; i <= m; i++)
             80         {
             81             cin >> relation;
             82             
             83             if(find)
             84                 continue;
             85             
             86             G.AddEdge(relation[0- 'A', relation[2- 'A');
             87             
             88             if(G.ExistCycle())
             89             {
             90                 cout << "Inconsistency found after " << i << " relations." << endl;
             91                 find = true;
             92                 continue;
             93             }
             94             
             95             int x[26];
             96             if(G.TopSort(x))
             97             {
             98                 cout << "Sorted sequence determined after " << i << " relations: ";
             99                 for(int i = n - 1; i >= 0; i--)
            100                     cout << char(x[i] + 'A');
            101                 cout << '.' << endl;
            102                 find = true;
            103             }
            104         }
            105         if(find == false)
            106             cout << "Sorted sequence cannot be determined." << endl;
            107     }
            108     
            109     return 0;
            110 }
            111 
            久久婷婷五月综合成人D啪| 国产91色综合久久免费| 久久天天躁狠狠躁夜夜2020| 久久精品亚洲福利| 久久一区二区免费播放| 亚洲伊人久久大香线蕉综合图片| 久久青青草原精品国产| 国产精品无码久久久久| 亚洲国产精品无码久久| 伊人久久大香线蕉精品不卡| 国产精品免费看久久久| 一本久久a久久精品亚洲| 精品一区二区久久久久久久网站| 久久天天躁夜夜躁狠狠躁2022| 久久天天躁狠狠躁夜夜躁2O2O| 尹人香蕉久久99天天拍| 国产精品久久影院| 久久综合九色综合网站| 亚洲性久久久影院| 国产亚洲美女精品久久久| 成人免费网站久久久| 99久久精品免费看国产一区二区三区 | 久久久久99精品成人片直播| 久久国产成人午夜AV影院| 精品久久久久久综合日本| 色偷偷88888欧美精品久久久| 久久国产精品无| 国内精品久久久久影院薰衣草| 一级做a爰片久久毛片人呢| 久久国产高清字幕中文| 亚洲中文久久精品无码| 性做久久久久久久久久久| 久久午夜无码鲁丝片秋霞| 亚洲国产天堂久久久久久| 国产精品九九久久免费视频 | 99久久国产综合精品五月天喷水 | 人妻中文久久久久| 无码人妻少妇久久中文字幕| 国产精品成人无码久久久久久| 国产亚洲婷婷香蕉久久精品| 久久精品www|