[BOJ] 1734. 교통 체계

문제

https://www.acmicpc.net/problem/1734

1734번: 교통 체계

 

풀이

DFS를 탐색하면서 각 노드 별로 다음 정보를 저장한다.

• sTime : 노드를 처음 만났을 때의 시간
• eTime : 자식 노드의 탐색을 모두 끝내고 노드를 빠져나올 때의 시간
• low : 해당 노드에서 DFS를 진행했을 때, 등장하는 노드들의 sTime의 최솟값
• depth : DFS spanning tree에서의 depth
• par : DFS spanning tree에서의 부모 노드
• adj : 인접리스트, 현재 노드와 연결된 노드의 정보
• child : DFS spanning tree에서의 자식 노드들

이제 쿼리를 분석해보자.

1) 1번 쿼리, $a,b,g_1,g_2$가 입력으로 들어온다.

만약 $g_1,g_2$가 DFS spanning tree의 tree edge가 아니라면, $a,b$는 DFS spanning tree로 연결된다.

 

일반성을 잃지 않고 $g_1$이 $g_2$의 parent라고 하자.

이 때, $g_1, g_2$ edge가 단절선이 아니면, 즉 $g_2$에서 $g_2$위로 가는 bypass가 있으면 그 bypass로 연결이 가능하다.

 

만약 $g_1, g_2$가 단절선이라면, $a,b$가 단절선을 기준으로 같은 쪽에 있는지를 확인하고, 같은 쪽에 있으면 단절 후에도 연결이 가능하다.

 

위의 경우가 모두 불가능하다면, $a,b$ 사이의 경로는 단절선을 통하는 경로 뿐이고 단절선을 끊으면 이동할 수 없다.

 

각각의 체크는 모두 $O(1)$만에 가능하다.

 

2) 2번 쿼리, $a,b,c$가 입력으로 들어온다.

만약 $a,b$가 둘 모두 DFS spanning tree 상에서 $c$의 자손이 아니라면, tree의 정의에 의해 c를 통하지 않는 $a$와 $b$사이의 경로가 존재한다.

 

만약 둘 모두 $c$의 자손이라면, $c$의 자식들 중에서 $a$와 $b$를 각각 포함하는 자식이 존재할 것이다.

이를 $ac, bc$라고 하자. ($a=ac, b=bc$일 수도 있다.)

만약 $ac=bc$라면 $c$가 $ac, bc$의 lca(lowest common ancestor)가 아니라는 뜻이므로, c가 없어져도 a와 b사이의 경로가 존재한다.

 

만약 위의 경우가 아니라면 $a,b$중 $c$의 자손인 노드는 $c$를 우회해서 갈수 있는지 체크하고, 자손이 아닌 노드끼리는 단절의 전후 상관없이 항상 연결이 가능하므로 자손인 노드만 $c$보다 빠른 점으로 가는 bypass가 있는지 확인해주면 된다.

 

각각의 처리는 대부분 $O(1)$에 가능하지만, $ac,bc$를 찾기 위해서 $c$의 child 목록에서 binary search를 통해 해당하는 child를 찾아야하므로 $O(log(\text{# child of c}))$만큼의 시간복잡도가 필요하고, 이는 최대 $O(logn)$ 만큼 필요하다.

 

Time Complexity : $O(n+q_1+q_2logn)$

 

코드

#include<iostream>
#include<vector>

using namespace std;

struct data
{
	int sTime;
	int eTime;
	int low;
	int depth;
	int par;
	vector<int> adj;
	vector<int> child;
};
vector<data> info;

int n,e,q;
int visitTime = 1;
void dfs(int now)
{
	data& d=info[now];
	d.sTime = d.low = visitTime++;
	for(vector<int>::iterator it=d.adj.begin();it!=d.adj.end();++it)
	{
		int nxt = *it;
		data& x = info[nxt];
		if(x.depth!=-1)
		{
			if(d.par!=nxt) d.low = min(d.low, x.sTime);
			continue;
		}
		x.depth = d.depth+1;
		x.par = now;
		d.child.push_back(nxt);
		dfs(nxt);
		d.low = min(d.low, x.low);
	}
	d.eTime = visitTime++;
}

bool isAncestor(int x1, int x2)
{
	return info[x1].sTime<=info[x2].sTime && info[x2].eTime <=info[x1].eTime;
}
bool bypass(int x1,int x2)
{
	return info[x1].low<info[x2].sTime;
}

int findChild(int x1, int x2)
{
	int l=0,r=info[x1].child.size()-1;
	while(l!=r)
	{
		int mid = (l+r)>>1;
		int now = info[x1].child[mid];
		if(info[x2].sTime > info[now].eTime) l=mid+1;
		else if(info[x2].eTime < info[now].sTime) r = mid-1;
		else return now;
	}
	return info[x1].child[l];
}
void yes()
{
	cout<<"yes\n";
}
void no()
{
	cout<<"no\n";
}
int main()
{
	cin.tie(NULL);
	cin.sync_with_stdio(false);
	cin>>n>>e;

	data init={0,0,0,-1,0,vector<int>(),vector<int>()};
	info.resize(n+1,init);
	while(e--)
	{
		int x,y;
		cin>>x>>y;
		info[x].adj.push_back(y);
		info[y].adj.push_back(x);
	}
	
	info[1].par = -1;
	info[1].depth = 1;

	dfs(1);

	cin>>q;
	while(q--)
	{
		int x,a,b;
		cin>>x>>a>>b;
		if(x==1)
		{
			int g1,g2;
			cin>>g1>>g2;
			if(isAncestor(g2,g1)) swap(g1,g2);

			if(info[g1].depth != info[g2].depth-1) yes();
			else if(bypass(g2,g2)) yes();
			else if(isAncestor(g2,a)==isAncestor(g2,b)) yes();
			else no();
		}
		else
		{
			int c;
			cin>>c;
			if(!isAncestor(c,a) && !isAncestor(c,b)) yes();
			else if(isAncestor(c,a) && isAncestor(c,b))
			{
				int ac = findChild(c,a);
				int bc = findChild(c,b);
				if(ac==bc)yes();
				else if(bypass(ac,c)&&bypass(bc,c)) yes();
				else no();
			}
			else
			{
				if(!isAncestor(c,a)) swap(a,b);
				int ac = findChild(c,a);
				if(bypass(ac,c)) yes();
				else no();
			}
		}
	}
}