gzwzm06

  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  1 随笔 :: 52 文章 :: 17 评论 :: 0 Trackbacks
  1 #include <cstdio>
  2 #include <memory>
  3 const int MAXN = 27 ;
  4 const int SIZE = 501 ;
  5 
  6 struct NODE
  7 {
  8     int ID ;
  9     NODE *next ;
 10 };
 11 
 12 NODE edge[MAXN] , g_Temp[SIZE] ;
 13 int g_Pos ;
 14 
 15 int num , n , gm ;
 16 int degree[MAXN] ;
 17 char seq[MAXN] ;
 18 bool visited[MAXN] ;
 19 
 20 //拓扑排序
 21 int TopSort(const int& NodeNum)
 22 {
 23     int Stack[MAXN] , top = -1 , i , flag , temp[MAXN] ;
 24     NODE *ptr = NULL ;
 25     
 26     flag = -2 ;
 27     gm = 0 ;
 28     //先找出初始状态下入度为0的点
 29     //如果有多个点则标志为-1
 30     for ( i = 0 ; i < MAXN ; ++i )
 31     {
 32         temp[i] = degree[i] ;
 33         if ( degree[i] == 0 && visited[i])
 34         {
 35             Stack[++top] = i ;
 36             if ( top > 0 )
 37                 flag = -1 ;            
 38         }
 39     }
 40     //记录序列,并判断是否有多个解存在
 41     while ( top != -1 )
 42     {
 43         seq[gm++= (char)(Stack[top] + 'A') ;
 44         ptr = edge[Stack[top--]].next ;
 45    
 46         while (ptr)
 47         {
 48             temp[ptr->ID]-- ;
 49             
 50             if ( temp[ptr->ID] == 0 )
 51             {
 52                 Stack[++top] = ptr->ID ;
 53                 if ( top > 0 ){
 54                     flag = -1 ;
 55                 }          
 56             }
 57             
 58             ptr = ptr->next ;
 59         }
 60     }
 61     //如果有环存在,则返回0
 62     if ( gm < NodeNum )
 63         return 0 ;
 64     //如果能确定序列,则返回1
 65     if ( gm == num && flag != -1 )
 66         flag = 1 ;
 67     
 68     return flag ;
 69 }
 70 
 71 void Insert( const int& x , const int& y )
 72 {
 73     NODE *tmp = &g_Temp[g_Pos++] ;
 74     tmp->ID = y ;
 75     tmp->next = edge[x].next ;
 76     edge[x].next = tmp ;
 77 }
 78 
 79 void Init()
 80 {
 81     int i ;
 82     for ( i = 0 ; i < MAXN ; ++i )
 83     {
 84         degree[i] = 0 ;
 85         visited[i] = false ;
 86         edge[i].next = NULL ;
 87     }
 88     
 89     g_Pos = 0 ;
 90     gm = 0 ;
 91 }
 92 int main()
 93 {
 94    // freopen("in", "r", stdin ) ;
 95     char inStr[5];
 96     int i , ia , ic , cnt , flag , ans ;
 97     bool circle ;   //标志是否有环
 98     
 99     while ( 1 )
100     {
101         scanf("%d %d"&num, &n) ;
102         if ( num == 0 || n == 0 )
103             break ; 
104         
105         Init() ;
106         cnt = 0 ;
107         ans = 1000 ; //由于没有输入过程中输出答案,所以需要加些标记
108         flag = -2 ;
109         circle = false ;
110         for ( i = 1 ; i <= n ; ++i )
111         {
112             scanf("%s"&inStr) ;
113             
114             ia = inStr[0- 'A' , ic = inStr[2- 'A' ;
115             
116             degree[ic]++ ;
117             
118             if ( !visited[ia] ){
119                 visited[ia] = true ;
120                 cnt++ ;
121             }
122             if ( !visited[ic] ){
123                 visited[ic] = true ;
124                 cnt++ ;
125             }
126         
127             Insert( ia, ic ) ;
128             
129             if ( flag != 1 )
130             {
131                 flag = TopSort( cnt ) ;
132                 if ( flag == 0 && ans > i )
133                 {
134                     ans = i ;
135                     circle = true ;
136                 }
137                 else if ( flag == 1 )
138                 {
139                     ans = i ;
140                 }
141             }            
142         }
143         //先确定有解
144         if ( flag == 1 )
145         {
146             seq[gm] = 0 ;
147             printf("Sorted sequence determined after %d relations: %s.\n", ans, seq) ;
148         }
149         else if ( circle )//在确定有环
150         {
151             printf("Inconsistency found after %d relations.\n", ans) ;
152         }
153         else {
154             printf("Sorted sequence cannot be determined.\n") ;
155         }      
156              
157     }
158     return 0 ;
159 }
160 

posted on 2008-11-13 17:39 阅读(498) 评论(0)  编辑 收藏 引用 所属分类: 图论

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理