CFR Educational 10 E. Pursuit For Artifacts ( Bridge BCC + Shrink Cycle )

http://codeforces.com/contest/652/problem/E
Shrink each bridge BCC to as a single vertex. If a treasure exists in some BCC, that BCC will be sure able to take that treasure. Otherwise a treasure might be on a bridge linking BCCs, and we will have to find around whether it is possible to take some treasure then reach to the dealer, with simple dfs.
Seems like my bridge bcc finding algorithm is too slow, for it is implemented with an extra flood fiil.

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 3e5 + 5;
const int MAXM = 3e5 + 5;
typedef pair< int, int > pii;

struct Edge{
    int u, v, z;
    Edge( int _u = -1, int _v = -1, int _z = -1 ): u(_u), v(_v), z(_z){}
} es[ MAXM << 1 ];

int n, m;
vector< int > G[ MAXN ];
int a, b;

set< pii > has_bridge;

int dfs_clock, low[ MAXN ], pre[ MAXN ];
int tarjan( int u, int fa ){
    int lowu = pre[ u ] = ++dfs_clock;
    for( int vidx : G[ u ] ){
        Edge &e = es[ vidx ];
        if( e.v == fa ) continue;
        if( !pre[ e.v ] ){
            int lowv = tarjan( e.v, u );
            if( lowv > pre[ u ] ){
                has_bridge.insert( pii( u, e.v ) );
                has_bridge.insert( pii( e.v, u ) );
            }
            lowu = min( lowu, lowv );
        } else if( pre[ e.v ] < pre[ u ] )
            lowu = min( lowu, pre[ e.v ] );
    }
    return low[ u ] = lowu;
}

int bcc_cnt, bccno[ MAXN ];
void floodfill( int s, int col ){
     queue< int > que;
     que.push( s );
     bccno[ s ] = col;
     while( !que.empty() ){
         int u = que.front(); que.pop();
         for( int vidx : G[ u ] ){
             Edge &e = es[ vidx ];
             if( bccno[ e.v ] ) continue;
             if( has_bridge.count( pii( u, e.v ) ) ) continue;
             que.push( e.v );
             bccno[ e.v ] = col;
         }
    }
}

vector< int > BG[ MAXN ]; // bcc graph
int bcc_has_art[ MAXN ]; // bcc has art in itself
set< pii > bridge_has_art;

void findBcc(){
    tarjan( 1, -1 );
    for( int u = 1; u <= n; ++u ) if( !bccno[ u ] )
        floodfill( u, ++bcc_cnt );
    for( int u = 1; u <= n; ++u ){
        for( int vidx : G[ u ] ){
            Edge &e = es[ vidx ];
            int bu = bccno[ u ], bv = bccno[ e.v ];
            if( bu == bv ){
                bcc_has_art[ bu ] |= e.z;
            } else{
                BG[ bu ].push_back( bv );
                BG[ bv ].push_back( bu );
                if( e.z )
                    bridge_has_art.insert( pii( bu, bv ) ),
                    bridge_has_art.insert( pii( bv, bu ) );
            }
        }
    }
}

bool dfs( int u, int fa, bool took ){
    took |= bcc_has_art[ u ];
    if( u == bccno[ b ] ) return took;
    for( int v : BG[ u ] ){
        if( v == fa ) continue;
        if( dfs( v, u, took | bridge_has_art.count( pii( u, v ) ) ) )
            return true;
    }
    return false;
}

void solve(){
    findBcc();
    if( dfs( bccno[ a ], -1, false ) ) puts("YES");
    else puts("NO");
}

int main(){
    scanf("%d%d", &n, &m);
    for( int i = 0; i < m; ++i ){
        int u, v, z; scanf("%d%d%d", &u, &v, &z);
        es[ i ] = Edge( u, v, z );
        es[ m + i ] = Edge( v, u, z );
        G[ u ].push_back( i );
        G[ v ].push_back( m + i );
    }
    scanf("%d%d", &a, &b);
    solve();
    return 0;
}