强连通分量

Posted by

Tarjan 模板

void tarjan(int u)
{
    pre[u] = lowlink[u] = ++dfs_clock;
    S.push(u);insta[u] = true;
    for (int i = head[u]; i; i = e[i].next)
    {
        int v = e[i].to;
        if ( !pre[v] )
        {
            tarjan(v);
            lowlink[u] = min(lowlink[u], lowlink[v]);
        }
        else if ( insta[v] )
        {
            lowlink[u] = min( lowlink[u], pre[v] );
        }
    }
    if ( lowlink[u] == pre[u] )
    {
        scc_cnt ++;
        for ( ;; )
        {
            int x = S.top(); S.pop();insta[x] = false;
            sccno[x] = scc_cnt;
            all[scc_cnt] ++;
            if ( x == u ) break;
        }
    }
}

Garbow 模板

int garbow(int u)
{
    stack1[++p1] = u;
    stack2[++p2] = u;
    low[u] = ++dfs_clock;
    for(int i = head[u]; i; i = e[i].next)
    {
        int v = e[i].to;
        if(!low[v]) garbow(v);
        else if(!sccno[v])
            while( low[stack2[p2]] > low[v] ) p2 --;
    }
    if( stack2[p2] == u)
    {
        p2 --;
        scc_cnt ++;
        do
        {
            sccno[stack1[p1]] = scc_cnt;
            //all_scc[scc_cnt] ++; 
        } while(stack1[p1--] != u) ;
    }
    return 0;
}

void find_scc(int n)
{
    dfs_clock = scc_cnt = 0;
    p1 = p2 = 0;
    memset(sccno, 0, sizeof(sccno));
    memset(low, 0, sizeof(low));
    for ( int i = 1; i <= n; i ++ )
        if ( !low[i] ) garbow(i);
}

[USACO03FALL][HAOI2006]受欢迎的牛 G

B2. Books Exchange (hard version)

Leave a Reply

电子邮件地址不会被公开。 必填项已用*标注