쌍연통분량의 구해

이중연통분량은 도론에서 중요한 모델로 그 구해 방식과 정수리의 차이가 많지 않다.코드에는 이중 연결 분량의 점을 하나의 창고로 저장합니다.주의, 여기서 말한 쌍연통분량은 점-쌍연통분량이다.다음은 핵심 코드입니다.

class edge
{
    public:
        int u;
        int v;
};
bool iscut[maxn];
vector<int>G[maxn];
vector<int>bcc[maxn];
stackS;
int n,m,low[maxn],pre[maxn],dfs_clock=0,bcc_cnt=0;
int bccno[maxn];

int dfs(int u,int fa)
{
    int lowu = pre[u] = ++dfs_clock;
    int child = 0;
    for(int i = 0;i < G[u].size();i++)
    {
        int v = G[u][i];
        edge e = (edge){u,v};
        if(!pre[v])
        {
            S.push(e);
            child++;
            int lowv = dfs(v,u);
            lowu = min(lowu,lowv);
            if(lowv >= pre[u])
            {
                iscut[u] = true;
                bcc_cnt++;
                bcc[bcc_cnt].clear();
                for(;;)
                {
                    edge& x = S.top();
                    S.pop();
                    if(bccno[x.u]!=bcc_cnt)
                    {
                        bcc[bcc_cnt].push_back(x.u);
                        bccno[x.u] = bcc_cnt;
                    }
                    if(bccno[x.v]!=bcc_cnt)
                    {
                        bcc[bcc_cnt].push_back(x.v);
                        bccno[x.v] = bcc_cnt;
                    }
                    if(x.u == u&&x.v == v)break;
                }
            }
        }
        else if(pre[v] < pre[u]&& v != fa)
        {
            S.push(e);
            lowu = min(lowu,pre[v]);
        }
    }
    if(fa < 0&&child==1)
        iscut[u] = false;
    low[u] = lowu;
    return lowu;
}

void find_bcc(int n)
{
    memset(pre,0,sizeof(pre));
    memset(bccno,0,sizeof(bccno));
    memset(iscut,0,sizeof(iscut));
    bcc_cnt = dfs_clock = 0;
    for(int i = 0 ; i < n ; i++ )
        if(!pre[i])
            dfs(i,-1);
}

코드가 좀 길다. 그 중 상당 부분은 빈칸, 리턴 따위인데 코드를 더욱 아름답게 하기 위해서다.PS: 블로거는 강박증이 있어 보기 싫은 코드를 보기 싫어한다.