[도 론] 절 변 과 다리, 쌍 연통 분량 과 강 연통 분량

절단 점 과 다리 절단 점: 한 점 과 그 와 관련 된 변 을 제거 하여 전체 그림 의 연결 지점 수 를 증가 시 키 면 이 점 은 바로 절단 점 이다.다리: 한 변 을 없 애고 전체 그림 의 연결 지점 수 를 증가 시 키 면 이 변 은 다리 입 니 다.tarjan 알고리즘 은 그림 에 없 는 절 점 을 구 합 니 다. low [u] 를 u 또는 u 로 정의 하 는 서브 트 리 가 거 슬러 올 라 갈 수 있 는 최초의 스 택 에서 노드 의 차 번 호 를 구 합 니 다. dfn [u] 는 노드 u 검색 의 순서 번호 (시간 스탬프) 입 니 다. 그러면 u 는 절 점 이 고 u 만 만족 할 때 ① u 는 dfs 검색 트 리 의 뿌리 이 며 u 는 2 그루 이상 의 서브 트 리 를 포함 합 니 다.② u 는 dfs 가 나무의 뿌리 를 검색 하 는 것 이 아니 라 부등식 low [v] > = dfn [u] 가 있 습 니 다. 그 중에서 (u, v) 는 나뭇가지 옆 입 니 다.이런 상황 에서 low [v] > = dfn [u] 가 설립 되 었 다. 즉, v 가 조상 에 게 도착 하려 면 반드시 u 를 통과 해 야 한다. 그렇지 않 으 면 다른 변 이 v 를 조상 에 게 도착 시 킬 수 있다 면 low [v] 는 dfn [u] 보다 작 을 것 이다. 그러면 이때 u 를 없 애 면 그림 의 연결 분기 수 는 반드시 증가 할 것 이다.   

void tarjan(int u,int root,int fa)    
{    
	    DFN[u]=low[u]=++index;    
	    instack[u]=1;    
	    int cnt=0;    
	    for(int i=head[u];i!=-1;i=edge[i].next)    
	    {    
	        int v=edge[i].to;    
	        if(!instack[v])    
	        {    
	            tarjan(v,root,u);    
	            cnt++;    
	            if(low[u]>low[v])//       low       low ，                  ，        low       。 
                low[u]=low[v];    
	            if(u==root && cnt>1)//  u        2   ,    。           ,         ，                      1 。         。 
	                {
	                	cut_point[u]=1; 
						add_block[u]++;	
					}    
	            else if(u!=root && low[v]>=DFN[u])//  u                          
	                {
						cut_point[u]=1;    
						add_block[u]++;
					}
	        }    
	        else if(v!=fa && low[u] > DFN[v])//           ，        low  
	            low[u]=DFN[v];    
	    }
} 

tarjan 알고리즘 은 그림 이 없 는 다 리 를 구 합 니 다:
변 (u, v) 은 그림 이 없 는 다리 이 고 (u, v) 만 low [v] > DFN [u] 를 만족 시 키 는 것 이다. 즉, 변 (u, v) 은 v 가 조상 에 게 도착 하 는 필수 적 인 길이 기 때문에 변 (u, v) 을 없 애 면 연결 분기 가 증가 하지만 u, v 사이 에 무 거 운 변 이 존재 하면 다리 가 아니다. 그래서 우 리 는 중 변 에 대해 판정 해 야 한다.

void Tarjan(int u,int pre)
{
    int v;
    Low[u] = DFN[u] = ++Index;
    Stack[top++] = u;
    Instack[u] = true;
    int son = 0;
    for(int i = head[u];i != -1;i = edge[i].next)
    {
        v = edge[i].to;
        if(v == pre)continue;
        if( !DFN[v] )
        {
            son++;
            Tarjan(v,u);
            if(Low[u] > Low[v])Low[u] = Low[v];
            // 
            //     (u,v)  ，    (u,v)    ，   DFS(u) DFN[u])
            {
                bridge++;
                edge[i].cut = true;
                edge[i^1].cut = true;
            }
            //  
            //    u   ，      (1) (2) (1) u   ， u       。
            //(2) u    ，     (u,v)    (     ，
            // u v        )，  DFS(u)<=Low(v)
            if(u != pre && Low[v] >= DFN[u])//    
            {
                cut[u] = true;
                add_block[u]++;
            }
        }
        else if( Low[u] > DFN[v])
             Low[u] = DFN[v];
    }
    //  ，     1
    if(u == pre && son > 1)cut[u] = true;
    if(u == pre)add_block[u] = son - 1;
    Instack[u] = false;
    top--;
}

tarjan 알고리즘 은 무방 향 그림 의 이중 연결 분량 을 구 합 니 다. 무방 향 연결 그림 에서 이 그림 의 어떤 결점 을 삭제 해도 이 그림 의 연결 성 을 바 꿀 수 없 으 면 이 그림 은 쌍방 향 연결 그림 입 니 다.두 개의 연결 분량 중 두 개의 정점 사이 에는 적어도 두 개의 교차 하지 않 는 경로 가 있 고 모든 low 가 같은 점 은 같은 두 개의 연결 분량 에 있다. 
예제: POJ 3177 은 연 결 된 무방 향 그림 G 를 지정 합 니 다. 최소한 몇 개의 변 을 추가 해 야 쌍 연결 그림 으로 바 꿀 수 있 습 니 다.

#include 
#include 
#include 
#include 
#include 

tarjan 알고리즘 은 그림 에 강 한 연결 분량 을 구 합 니 다:
 한 그림 의 서브 맵 에서 임의의 두 점 이 서로 도달 할 수 있다. 즉, 서로 통 하 는 경로 가 존재 한다. 그러면 이 서브 맵 은 바로 강 한 연결 분량 (또는 강 한 연결 지점 이 라 고 함) 이다.
 만약 방향 도 가 있 는 임의의 두 점 이 서로 도달 할 수 있다 면 이 그림 을
강연 통도.강 한 연통 분량 을 구 하 는 과정 은 이전 과 유사 하 다.dfn [u] = = low [u] 일 때 스 택 꼭대기 에서 u 까지 의 노드 는 모두 같은 강 한 연결 분량 에 속 합 니 다. 이때 스 택 에서 u 가 나 올 때 까지 계속 나 오 면 됩 니 다. 
 

const int maxn=10005;  
int DFN[maxn];//              
int low[maxn];//                     （            ）  
int stack[maxn];  
int sccnum[maxn];//                 
bool instack[maxn];  
int sccNum;//          
int top;  
int index;  
int n;  
struct node  
{  
    int to;  
    int next;  
}edge[10*maxn];  
int head[maxn];  
int tot;  
void addedge(int from,int to)  
{  
    edge[tot].to=to;  
    edge[tot].next=head[from];  
    head[from]=tot++;  
}  
void tarjan(int u)  
{  
    DFN[u]=low[u]=++index;//       ，DFN low             
    stack[top++]=u;//    
    instack[u]=1;  
    for(int j=head[u];j!=-1;j=edge[j].next)  
    {  
    	int v=edge[j].to;
        if(!DFN[v])//          
        {  
            tarjan(v);  
            if(low[u]>low[v]) low[u]=low[v]; //    low     ,  i  i                     
        }  
        else if(instack[v])//      
        {  
            if(low[u]>DFN[v])  low[u]=DFN[v];  
        }  
    }  
    if(DFN[u]==low[u])//     
    {  
        sccNum++;  
        do  
        {  
            int v=stack[--top];  
            sccnum[v]=sccNum;  
            instack[v]=0;//      
        }while(v!=u);  
    }  
}  
void solve()  
{  
    memset(DFN,0,sizeof(DFN));  
    memset(instack,0,sizeof(instack));  
    index=0;  
    sccNum=0;  
    top=0;  
    for(int i=1;i<=n;i++)  
        if(!DFN[i])  
            tarjan(i);  
}  
  
int main()  
{  
    int m,a,b;  
    while(~scanf("%d%d",&n,&m))  
    {  
        if(n==0 && m==0)  
            break;  
        memset(head,-1,sizeof(head));  
        tot=0;  
        for(int i=0;i