Tarjan 3 대 알고리즘 의 이중 연결 분량 (이중 연결 분량)

정의: 하나의 연결 그림 에 대해 임의의 두 점 에 적어도 두 개의 점 이 중복 되 지 않 는 경로 가 존재 한다 면 이 그림 을 점 쌍 연결 (쌍 연결 이 라 고 약칭) 이 라 고 부른다.만약 임의의 두 점 에 적어도 두 개의 변 이 중복 되 지 않 는 경로 가 존재 한다 면 이 그림 을 변 쌍 연결 이 라 고 부른다.점 쌍 연통 도의 정 의 는 임 의 두 변 이 모두 하나의 간단 한 고리 에 있 는 것 과 같 고 변 쌍 연통 도의 정 의 는 임 의 한 변 이 적어도 하나의 간단 한 고리 에 있 는 것 과 같다.무 방향 도, 점 쌍 연통 의 극 대 자 도 를 점 쌍 연통 분량 (약칭 쌍 연통 분량) 이 라 고 하고, 변 쌍 연통 의 극 대 자 도 를 변 쌍 연통 분량 이 라 고 한다.이 블 로 그 는 무 방향 도 점 쌍 연결 분량 과 변 쌍 연결 분량 을 정리 하 는 방법 이다.
알고리즘: 구 해 점 쌍 연통 분량 과 변 쌍 연통 분량 은 사실 구 해 절단 점 과 다리 와 밀접 한 관 계 를 가진다.서로 다른 이중 연결 분량 은 최대 한 개의 공공 점, 즉 어떤 절단 지붕 만 있 고 임의의 절단 지붕 은 적어도 두 개의 점 이 이중 으로 연 결 된 공공 점 이다.서로 다른 점 의 쌍 연결 분량 은 공공 점 이 없고 다 리 는 그 어떠한 변 의 쌍 연결 분량 에 있 지 않 으 며 점 의 쌍 연결 분량 은 반드시 한 변 의 쌍 연결 분량 이다.다음은 먼저 쌍 연결 분량 의 Tarjan 알고리즘 을 소개 합 니 다. 이전 블 로그 에서 우 리 는 지붕 을 자 르 는 방법 을 알 고 있 습 니 다. 쉽게 알 수 있 습 니 다. 우리 가 지붕 을 자 르 는 것 을 찾 았 을 때 이미 어떤 큰 쌍 연결 서브 맵 에 대한 방문 을 완 성 했 습 니 다. 그러면 우리 가 DFS 를 진행 하 는 과정 에서 옮 겨 다 니 는 점 을 저장 하면더 블 연결 분량 을 얻 을 수 있 지 않 을까요?알고리즘 을 실현 하기 위해 우 리 는 지붕 을 자 르 는 과정 에서 한 스 택 으로 옮 겨 다 니 는 사 이 드 를 저장 할 수 있 습 니 다 (주의 점 이 아 닙 니 다!). 그 후에 한 점 의 더 블 연결 분량, 즉 하위 노드 v 와 부모 노드 u 가 관계 low [v] > = dfn [u] 를 만족 시 킬 때마다 우 리 는 스 택 안의 물건 을 현재 사 이 드 를 만 날 때 까지 꺼 낼 수 있 습 니 다.여기 서 스 택 에 넣 는 것 은 점 이 아니 라 변 입 니 다. 이것 은 점 의 쌍 연결 분량 이 중복 점 이 존재 하기 때 문 입 니 다. 만약 에 우리 가 스 택 에 넣 은 것 이 점 이 라면 어떤 점 의 쌍 연결 분량 에 대해 서 는 점 이 조금 줄 어 들 것 입 니 다 (이 점 들 은 모두 지붕 을 자 르 는 것 입 니 다).코드:

struct Edge{
    int u,v;
    Edge(int u=0,int v=0):u(u),v(v){}
}e[maxm];
int n,m,stamp,dfn[maxn],low[maxn],iscut[maxn],bccno[maxn];
int scnt,stack[maxm],bcc_cnt;
vector<int> vec[maxn],bcc[maxn];

void tarjan(int index,int fa)
{
    int child=0,tmp;
    dfn[index]=low[index]=++stamp;
    for(int i=0;i<vec[index].size();i++)
    {
        tmp=e[vec[index][i]].v;
        if(!dfn[tmp])
        {
            stack[++scnt]=vec[index][i],child++;
            tarjan(tmp,index);
            low[index]=min(low[index],low[tmp]);
            if(low[tmp]>=dfn[index])
            {
                iscut[index]=1;
                bcc[++bcc_cnt].clear();
                while(1)
                {
                    int num=stack[scnt--];
                    if(bccno[e[num].u]!=bcc_cnt)
                    {
                        bcc[bcc_cnt].push_back(e[num].u);
                        bccno[e[num].u]=bcc_cnt;
                    }
                    if(bccno[e[num].v]!=bcc_cnt)
                    {
                        bcc[bcc_cnt].push_back(e[num].v);
                        bccno[e[num].v]=bcc_cnt;
                    }
                    if(e[num].u==index && e[num].v==tmp)
                        break;
                }
            }
        }
        else if(dfn[tmp]<dfn[index] && tmp!=fa)
        {
            stack[++scnt]=vec[index][i];
            low[index]=min(low[index], dfn[tmp]);
        }
    }
    if(fa<0 && child==1)
        iscut[index]=0;
}

void find_bcc()
{
    //    bccno     
    memset(dfn,0,sizeof(dfn));
    memset(low,0,sizeof(low));
    memset(iscut,0,sizeof(iscut));
    memset(bccno,0,sizeof(bccno));
    memset(bcc,0,sizeof(bcc));
    stamp=scnt=bcc_cnt=0;
    for(int i=1;i<=n;i++)
        if(!dfn[i])
            tarjan(i,-1);
}

여기 서 매우 주의해 야 할 것 은 알고리즘 이 끝 난 후에 모든 노드 에 하나의 번호 가 있 는데 이것 은 어느 점 의 쌍 연결 분량 에 속 하 는 지 대표 하 는 것 이다. 그러나 지붕 을 자 르 는 번 호 는 전혀 의미 가 없다!이 알고리즘 은 두 개의 시간 스탬프 와 스 택 을 유연 하 게 사용 하여 점 쌍 연결 분량 의 발견 을 완성 하 였 다.예제: UVALIVE 5135
그 다음 에 사 이 드 더 블 연결 분량 의 풀이 알고리즘 을 소개 했다. 사 이 드 더 블 연결 분량 의 구 해 는 매우 간단 하 다. 사 이 드 더 블 연결 분량 사이 에 공공 변 이 없고 다리 가 임의의 사 이 드 더 블 연결 분량 에 있 지 않 기 때문에 알고리즘 은 매우 간단 하 다. 즉, 먼저 DFS 에서 모든 다 리 를 찾 고 다시 DFS (다리 제외) 에서 사 이 드 더 블 연결 분량 을 찾 는 것 이다.PS: 당연히 DFS 로 한 번 실현 할 수 있 습 니 다.코드:

struct Edge{
    int u,v;
    Edge(int u=0,int v=0):u(u),v(v){}
}e[maxm];
int n,m,stamp,dfn[maxn],low[maxn],bccno[maxn],bcc_cnt;
vector<int> vec[maxn],bcc[maxn];
bool g[maxn][maxn],isbridge[maxm];

void tarjan(int index,int fa)
{
    int tmp;
    dfn[index]=low[index]=++stamp;
    for(int i=0;i<vec[index].size();i++)
    {
        tmp=e[vec[index][i]].v;
        if(!dfn[tmp])
        {
            tarjan(tmp,index);
            low[index]=min(low[index],low[tmp]);
            if(low[tmp]>dfn[index])
                isbridge[vec[index][i]]=isbridge[vec[index][i]^1]=1;
        }
        else if(dfn[tmp]<dfn[index] && tmp!=fa)
        {
            low[index]=min(low[index], dfn[tmp]);
        }
    }
}

void dfs(int index)
{
    dfn[index]=1;
    bccno[index]=bcc_cnt;
    for(int i=0;i<vec[index].size();i++)
    {
        int tmp=vec[index][i];
        if(isbridge[tmp])
            continue;
        if(!dfn[e[tmp].v])
        {
            dfs(e[tmp].v);
        }
    }
}

void find_ebcc(){
    bcc_cnt=stamp=0;
    memset(dfn,0,sizeof(dfn));
    memset(low,0,sizeof(low));
    memset(isbridge,0,sizeof(isbridge));
    memset(bccno,0,sizeof(bccno));
    memset(bcc,0,sizeof(bcc));
    for(int i=1;i<=n;i++)
        if(!dfn[i])
            tarjan(i, -1);
    memset(dfn,0,sizeof(dfn));
    for(int i=1;i<=n;i++)
    {
        if(!dfn[i])
        {
            bcc_cnt++;
            dfs(i);
        }
    }               
}

예제: POJ 3352