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

UVa Online Judge

```#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;
}
```