【Live Archive】6393 Self-Assembly【强连通】

本文主要是介绍【Live Archive】6393 Self-Assembly【强连通】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

传送门：【Live Archive】6393 Self-Assembly

题目分析：

假设我们只用到向上或者向右的块，这样我们只要找到一个回路使得某个块可以和第一个块一样，那么我们就相当于找到了一个循环，这样就可以无限循环了。

但是我们要怎样去找这么一个环？考虑到必须是对应字母 $X^+,X^-$ 才能建边，然后一个环中一定是多个一对一对的这样的对应字母组成的。

可以发现块的数量那么大也是无所谓的，因为我们用到的有用的信息只是块中的四个变量。考虑到一个块中有 $A^+,B^-,C^-,D^+$ ，那么我们可以建立有向边 $A^+\to B^+,B^-\to A^-$ 。表示有 $A^+$ 的块可以和有 $B^+$ 的块相连，有 $B^-$ 的块可以和有 $A^-$ 的块相连。其他边同理。

然后我们只要找到一个环就可以说明存在无限循环了。

PS：其实找环这一个过程用不到求强连通的= =，只不过我脑残了写了一个强连通，拓扑什么的其实更简单，只是我太懒了不想重写了。

$my~~code:$

#include <stdio.h>
#include <string.h>
#include <set>
#include <map>
#include <math.h>
#include <vector>
#include <algorithm>
using namespace std ;typedef long long LL ;#define clr( a , x ) memset ( a , x , sizeof a )
#define cpy( a , x ) memcpy ( a , x , sizeof a )const int MAXN = 100 ;
const int MAXE = 1000005 ;struct Edge {int v , n ;Edge () {}Edge ( int v , int n ) : v ( v ) , n ( n ) {}
} ;Edge E[MAXE] ;
int H[MAXN] , cntE ;
int S[MAXN] , top ;
char s[MAXN] ;
int scc[MAXN] , scc_cnt ;
int vis[MAXN][MAXN] ;
int ok ;
int dfn[MAXN] , low[MAXN] , dfs_clock ;
int n ;void init () {cntE = 0 ;dfs_clock = 0 ;scc_cnt = 0 ;clr ( scc , 0 ) ;clr ( dfn , 0 ) ;clr ( H , -1 ) ;
}void addedge ( int u , int v ) {E[cntE] = Edge ( v , H[u] ) ;H[u] = cntE ++ ;
}void tarjan ( int u ) {dfn[u] = low[u] = ++ dfs_clock ;S[top ++] = u ;for ( int i = H[u] ; ~i ; i = E[i].n ) {int v = E[i].v ;if ( !dfn[v] ) {tarjan ( v ) ;low[u] = min ( low[u] , low[v] ) ;} else if ( !scc[v] ) {low[u] = min ( low[u] , dfn[v] ) ;}}if ( dfn[u] == low[u] ) {++ scc_cnt ;int x = 0 ;do {scc[S[-- top]] = scc_cnt ;++ x ;} while ( S[top] != u ) ;if ( x > 1 ) ok = 1 ;}
}void solve () {init () ;ok = 0 ;for ( int i = 1 ; i <= n ; ++ i ) {scanf ( "%s" , s ) ;top = 0 ;for ( int j = 0 ; j < 8 ; j += 2 ) {char a = s[j] ;char b = s[j + 1] ;if ( a == '0' ) continue ;int x = a - 'A' ;if ( b == '-' ) S[top ++] = x << 1 ;else S[top ++] = x << 1 | 1 ;}for ( int j = 0 ; j < top ; ++ j ) {for ( int k = j + 1 ; k < top ; ++ k ) {int x = S[j] ;int y = S[k] ;if ( x == ( y ^ 1 ) ) ok = 1 ;addedge ( x , y ^ 1 ) ;addedge ( y , x ^ 1 ) ;}}}top = 0 ;for ( int i = 1 ; i < 52 ; ++ i ) {if ( !dfn[i] ) tarjan ( i ) ;if ( ok ) break ;}if ( ok ) printf ( "unbounded\n" ) ;else printf ( "bounded\n" ) ;
}int main () {while ( ~scanf ( "%d" , &n ) ) solve () ;return 0 ;
}