[Codeforces 1144F] Graph Without Long Directed Paths

[Codeforces 1144F] Graph Without Long Directed Paths

Problem - F - Codeforces

유형 : DFS, graph

 

문제 설명 : 

입력으로 vertex가 n개이고 u와 v를 연결하는 undirectd인 간선이 m개 주어진다. 이 간선들을 directed로 전환해서 그래프에 길이가 2이상인 경로가 없도록 만들어야 한다. 어떻게 전환해도 불가능한 경우에는 "NO"를 출력하고, 가능하다면 "YES"와 함께 입력에서 주어진 간선의 정보 (u->v)를 그대로 전환한다면 0을 출력하고, 그와 반대인 (v->u)로 전환한다면 1을 출력하는 문제이다.

 

풀이 : 

예전에 푼 적이 있는 [Codeforces 1093D] Beautiful Graph 와 비슷한 유형의 문제이다. 아무 노드에서부터 dfs로 모든 노드를 순회하면서 각 노드에 type을 지정해준다. type는 1과 2 두개로만 이루어지며 현재 노드의 타입은 반드시 인접한 그것과 인접한 노드의 타입과 달라야 한다. 예를 들어 이전 노드의 type이 1이었다면 현재 노드는 2이고, 이전이 2였다면 현재는 1이 되어야 하는, 그런 식이다. 이 방식으로 type을 매기는데 충돌이 생길 수도 있다. 예를 들어 삼각형모양처럼 (1,2),(2,3),(3,1)이면 어느 한 노드는 충돌이 생길 수도 있다. 이런 경우는 불가능한 경우이므로 "NO"라고 처리를 한다. 만약 아무 충돌 없이 type을 지정했다면, 1번 타입은 0으로 출력하고, 2번 타입은 1로 출력하면 된다(사실 반대로 해도 상관 없다).

이 풀이가 성립하는 이유는 길이가 2이상인 경로를 없애기 위해서는 각 노드의 indegree와 outdegree의 수와 상관이 있다. 길이가 2이상인 경로를 없애기 위해서는 모든 노드는 indegree와 outdegree가 동시에 1 이상이면 안된다. 반드시 indegree 혹은 outdegree 하나만 1이상이어야 한다. 동시에 1 이상인 값이라는 뜻은 들어오는 간선과 나가는 간선이 모두 존재한다는 의미이므로, 이는 곧 길이가 2인 경로가 존재함을 의미한다. 따라서 인접한 노드 간에 서로 다른 종류의 type을 지정함으로써 하나는 in만, 다른 하나는 out degree만 배정했다고 볼 수 있다.

 

주의할 점 : 

원래 그래프 문제는 disjoint 상태를 고려해야 하는데 이 문제는 친절하게 모든 노드들은 connected 되어있다고 명시되어 있다. 따라서 disjoint를 고려할 필요는 없다.

 

배운 점 : 

.

 

코드 : 

const int SIZE= 200009;
int V,E;
vector<int> graph[SIZE];
int type[SIZE]={0};
int ans=0;
vector<pii> q;
void dfs(int node,int cur_type){ //1 : in, 2:out
	type[node]=cur_type;
	for(int next:graph[node]){
		if(!type[next]){
			dfs(next,cur_type^3);
		}
		else{
			if(type[next]!=(cur_type^3)){
				ans=-1;
				return;
			}
		}
	}
	return;
}
int main(){
	scanf("%d %d",&V,&E);

	for(int i=0 ; i<E ; i++){
		int a,b;	scanf("%d %d",&a,&b);
		q.push_back({a,b});
		graph[a].push_back(b);
		graph[b].push_back(a);
	}

	dfs(1,1);
	if(ans==-1){
		printf("NO\n");
		return 0;
	}
	printf("YES\n");
	for(auto here:q){
		int fir=here.first,sec=here.second;

		if(type[fir]==1){ //
			printf("1");
		}
		else{
			printf("0");
		}
	}
	
	return 0;
}