POJ 1094 C++ （圖論）

//用DFS進行拓撲排序，超時 ，只能重寫
#include"stdio.h"
#include"string.h"
#include"stdlib.h"

int map[26][26],v[26],used[26],flag,n,total;
char str[27];
void sort(int i,int m)
{ int k;
if(total==n)
     {  flag=2;
          return ;
      }  
for(k=0;k<n && !flag;k++)
      { if(map[i][k]==0)
           continue;
       if(v[k])
          { flag=1;
             return ;
           }
       str[m]=k+65;    
       total++;
       v[k]=1;  
       sort(k,m+1);
       if(flag)
          return ;
       v[k]=0;
       total--;
      }
}                


int main()
{int row,i,j,a,b,k,l;
char s[4];
   freopen("in.txt","r",stdin);
   freopen("out.txt","w",stdout);
while(1)
  { scanf("%d%d",&n,&row);
     if(n==0 && row==0)
        break;

     flag=0;
     memset(map,0,sizeof(map));
     memset(used,0,sizeof(used));
     for(k=1;k<=row;k++)
         { scanf("%s",s);
          if(!flag)
           {memset(v,0,sizeof(v));
            a=s[0]-65;
            b=s[2]-65;
            used[a]=1;
            used[b]=1;
            map[a][b]=1;
            for(i=0;i<n && !flag;i++)
               {  if(used[i]==0)
                     break;
                    total=1;
                    v[i]=1;
                    str[0]=i+65;
                    sort(i,1);
                    v[i]=0;
               }

             if(flag==1)      
              printf("Inconsistency found after %d relations.\n",k);    
             else if(flag==2)
               {printf("Sorted sequence determined after %d relations: ",k);
                       for(i=0;i<n;i++)
                          printf("%c",str[i]);
                         printf(".\n");
                         flag=1;
               }  
          }
     }                

   if(!flag)
      printf("Sorted sequence cannot be determined.\n");

   }

return 0;
}              



// 改用floyd_warshall算法才過
#include"stdio.h"
#include"string.h"
#include"stdlib.h"
typedef struct Node{
        int d;
        char c;
}Node;            
int map[26][26],used[26],flag,n;
Node node[26];

int cmp(const void *a, const void *b)
{ return (*(Node *)a).d-(*(Node *)b).d;
}


void check()
{int i,j;
for(i=0;i<n;i++)
     { if(used[i]==0)
           return ;
       for(j=0;j<n;j++)
           if(map[i][j])
             node[j].d++;
     }
   qsort(node,n,sizeof(Node),cmp);
    for(i=0;i<n;i++)
        if(node[i].d!=i)
           return ;
        flag=2;
}    
int main()
{int row,i,j,a,b,k,h;
char s[4];
   freopen("in.txt","r",stdin);
   freopen("out.txt","w",stdout);
while(1)
  { scanf("%d%d",&n,&row);
     if(n==0 && row==0)
        break;
     flag=0;
     memset(map,0,sizeof(map));
     for(h=1;h<=row;h++)
         { scanf("%s",s);
           if(!flag)
           {a=s[0]-65;
            b=s[2]-65;
            used[a]=1;
            used[b]=1;
            for(i=0;i<n;++i)
                {node[i].d=0;
                 node[i].c=i+65;
                 }
         if(map[b][a]==1 || a==b)
             { printf("Inconsistency found after %d relations.\n",h);
               flag=1;
             }
          else
               map[a][b]=1;
          for(k=0;k<26;++k)
                for(i=0;i<26;++i)
                   for(j=0;j<26;++j)
                     map[i][j]=(map[i][j]||(map[i][k]&&map[k][j]));

        if(!flag)
            check();
        if(flag==2)
             {printf("Sorted sequence determined after %d relations: ",h);
                  for(i=0;i<n;i++)
                      printf("%c",node[i].c);
                     printf(".\n");

             }  
          }
     }                

   if(!flag)
      printf("Sorted sequence cannot be determined.\n");

   }

return 0;
}

posted on 2008-11-27 00:22 蝸牛 閱讀(1431) 評論(0)  編輯 收藏 引用 所屬分類: ACM ICPC