이중 결합 요소 (Biconnected Component)

Biconnected Component는 biconnected (단절점이 없는) maximal subgraph이다.

BCC는 그래프를 단절점/단절선을 기준으로 쪼갠 후, 이를 기준으로 정점/간선들을 묶어 트리로 만든다.

크게 2가지의 BCC가 있다.

1. Edge disjoint BCC = 단절점을 기준으로 쪼갠 간선의 집합

2. Vertex disjoint BCC = 단절선을 기준으로 쪼갠 정점의 집합

 

Vertex disjoint BCC의 경우에는 단절선을 모두 자른 후, 남은 컴포넌트들이 하나의 BCC를 구성하고, 이를 하나의 정점으로 압축한다면 트리가 된다.

 

Edge disjoint BCC의 경우에는 BCC가 간선의 집합으로 구성되어 있기 때문에, 한 정점은 여러 개의 BCC에 포함될 수 있다. 특히, 그러한 정점들은 모두 단절점이다.

한 정점이 여러 개의 BCC에 포함될 수 있다는 점 때문에 이 경우에는 단순히 정점들을 압축하는 것으로 트리를 만들 수 없다. 따라서, 트리를 각 색별 BCC를 대표하는 노드 하나와, 이 노드에 해당 BCC에 속하는 정점들을 성게 모양으로 연결하여 원래 그래프의 노드들과 BCC 색 노드들이 이분적으로 연결되어 있는 트리의 꼴이 나오게 된다.

 

BCC는 다음을 만족한다.

1. 간선 e1, e2가 같은 BCC에 속하기 위한 필요충분조건은 e1, e2를 동시에 포함하는 단순 사이클이 존재한다는 것이다. (Edge disjoint BCC)

2. 정점 v1, v2가 같은 BCC에 속하기 위한 필요충분조건은 v1, v2를 동시에 포함하는 단순 사이클이 존재한다는 것이다. (Vertex disjoint BCC)

3. 단절선의 양 끝의 정점들은 단절점이다.

 

색을 칠하는 알고리즘은 다음과 같다.

가장 먼저, 각 정점의 dfn과 low 값들을 전처리해놓는다. 이 때 부모 간선은 따라 올라가지 않도록 주의한다.

이제, dfs를 돌면서 현재 방문한 정점의 부모 간선의 색까지 결정했다고 하자. 어떤 자식 노드로 이어지는 간선이 현재 부모 간선과 같은 색이기 위해서는, 이 둘을 동시에 포함하는 단순 사이클이 존재해야 하고, 이는 즉 low[nxt]<dfn[now]를 의미한다. 이 경우에는 같은 색으로 계속해서 서브트리를 칠해 나가면 되고, 이 외의 경우에는 새로운 색을 하나 만든 뒤, 지금의 자식 노드로의 간선부터는 이 색으로 색칠해주면 된다.

int N, M;
vector<int> adj[MAXN+10];
 
int dfn[MAXN+10], low[MAXN+10], cnt;
 
void dfs(int now, int bef)
{
	low[now]=dfn[now]=++cnt;
	for(int nxt : adj[now])
	{
		if(nxt==bef) continue;
		if(dfn[nxt]) low[now]=min(low[now], dfn[nxt]);
		else
		{
			dfs(nxt, now);
			low[now]=min(low[now], low[nxt]);
		}
	}
}
 
int bcnt, vis[MAXN+10];
vector<int> bcc[MAXN+10];
 
void dfs2(int now, int col)
{
	if(col) bcc[now].push_back(col);
	vis[now]=true;
	for(int nxt : adj[now])
	{
		if(vis[nxt]) continue;
		if(low[nxt]>=dfn[now])
		{
			bcc[now].push_back(++bcnt);
			dfs2(nxt, bcnt);
		}
		else
		{
			dfs2(nxt, col);
		}
	}
}

int main()
{
	for(int i=1; i<=N; i++) if(dfn[i]==0) dfs(i, i);
	for(int i=1; i<=N; i++) if(vis[i]==0) dfs2(i, 0);
 
	for(int i=1; i<=N; i++)
	{
		if(bcc[i].size()==1)
		{
			sz[bcc[i][0]+N]++;
		}
		else
		{
			sz[i]++;
			for(auto nxt : bcc[i])
			{
				int u=i, v=nxt+N;
				adj2[u].push_back(v);
				adj2[v].push_back(u);
			}
		}
	}
}