uvaLA4255 Guess BFS+拓扑排序

算法指南白书

思路：“连续和转化成前缀和之差”

 #include <stdio.h>
 #include <string.h>
 #include <iostream>
 #include <algorithm>
 #include <vector>
 #include <queue>
 #include <set>
 #include <map>
 #include <cstring>
 #include <math.h>
 #include <stdlib.h>
 #include <time.h>
 using namespace std;
 const int maxn=;
 int T,n;
 int fa[];
 char str[][],s[];
 int G[][];
 int c[];
 vector<int>topo; int findset(int x){//并查集求祖先
     return fa[x]!=x?fa[x]=findset(fa[x]):x;
 }
 bool dfs(int u){//拓扑排序
     c[u]=-;
     for(int i=;i<=n;i++){
         if(G[u][i]){
             if(c[i]<)
                 return false;
             if(c[i]==)
                 dfs(i);
         }
     }
     c[u]=;
     topo.push_back(u);
     return true;
 }
 bool toposort(){
     topo.clear();
     memset(c,,sizeof(c));
     for(int i=;i<=n;i++){
         if(!c[i]){
             if(!dfs(i))
                 return false;
         }
     }
     reverse(topo.begin(),topo.end());
     return true;
 }
 int main(){
     scanf("%d",&T);
     while(T--){
         scanf("%d",&n);
         getchar();
         scanf("%s",s);
         int index=;
         for(int i=;i<=n;i++) fa[i]=i;
         for(int i=;i<=n;i++){
             for(int j=i;j<=n;j++){
                str[i][j]=s[index++];
                if(str[i][j]=='')
                    fa[j]=i-;//i-1和j同祖先
             }
         }
         memset(G,,sizeof(G));
        for(int i=;i<=n;i++){//sum[i]<sum[j],i到j连一条边
               for(int j=i;j<=n;j++){
                   if(str[i][j]=='-')
                       G[findset(j)][findset(i-)]=;
                if(str[i][j]=='+')
                 G[findset(i-)][findset(j)]=;
            }
        }
        toposort();
        int sum[];
        memset(sum,,sizeof(sum));
        int cur=;
        for(int i=;i<=n;i++){//0到。。。赋值
            sum[topo[i]]=cur++;
        }
        for(int i=;i<=n;i++){
            sum[i]=sum[findset(i)];
               if(i>)
                printf(" ");
                printf("%d",sum[i]-sum[i-]);
        }
        printf("\n");
     }
     return ;
 }