UVA 1423 Guess ( 拓撲排序 + 並查集 )

UVa Online Judge
用前綴和去想，若矩陣某個 ( i, j ) 為 +, 代表 pa( j ) - pa( i - 1 ) > 0, 同時意味著 pa( i - 1 ) < pa( j ), 那我們就給 ( i - 1 ) -> ( j ) 建有向邊，最後的拓撲序就能是他們合法的大小關係。比較特別的是當pa( j ) - pa( i - 1 ) == 0 的時候，因為這代表 pa( j ) == pa( i - 1 )，我們就必須視它們為一體，這時候我們結論就出來了，用並查集先把前綴和相同的節點都並起來成為一塊，之後建邊和輸出的時候也把同一塊的節點的前綴和都當相同的就可以了。

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 10 + 5;

int fa[MAXN];
int find(int x){ return fa[x] == x ? x : fa[x] = find( fa[x] ); }
void unite(int x, int y){
    int fx = find( x ), fy = find( y );
    if( fx != fy ) fa[ fx ] = fy;
}

int n;
char buf[MAXN * MAXN];
vector<int> G[MAXN];

int vis[MAXN];
stack<int> topo_stk;
bool dfs(int u){
    vis[ u ] = -1; // visiting
    for(int v: G[u]){
        if( vis[ v ] == -1 ) return false; // cycle exists
        if( !vis[ v ] && !dfs( v ) ) return false;
    }
    topo_stk.push( u );
    vis[ u ] = 1;
    return true;
}
bool toposort(){
    memset( vis, 0, sizeof(vis) );
    while( !topo_stk.empty() ) topo_stk.pop();
    for(int i = 0; i <= n; ++i)
        if( !vis[ i ] )
            if( !dfs( i ) )
                return false;
    return true;
}

int pa[MAXN];
void solve(){
    assert( toposort() );
    for(int i = 1; !topo_stk.empty(); ++i){
        pa[ topo_stk.top() ] = i;
        topo_stk.pop();
    }
    for(int i = 1; i <= n; ++i)
        printf("%d%c", pa[ find( i ) ] - pa[ find( i - 1 ) ], i == n ? '\n' : ' ');
}

void init(){
    for(int i = 0; i <= n; ++i)
        G[i].clear();
    for(int i = 0; i <= n; ++i)
        fa[i] = i;
}

int main(){
    int T; scanf("%d", &T);
    while( T-- ){
        scanf("%d%s", &n, buf);
        init();
        int bcnt = 0;
        for(int i = 1; i <= n; ++i)
            for(int j = i; j <= n; ++j)
                if( buf[ bcnt++ ] == '0' ) // pa[j] == pa[i - 1]
                    unite( i - 1, j );
        bcnt = 0;
        for(int i = 1; i <= n; ++i)
            for(int j = i; j <= n; ++j){
                if( buf[ bcnt ] == '+' ){ // pa[j] - pa[i - 1] > 0
                    // pa[i - 1] < pa[j] => ( i - 1 ) -> ( j )
                    G[ find( i - 1 ) ].push_back( find( j ) );
                } else if( buf[ bcnt ] == '-' )
                    G[ find( j ) ].push_back( find( i - 1 ) );
                ++bcnt;
            }
        solve();
    }
    return 0;
}