BOJ 9466 - 텀 프로젝트

• 모든 노드의 out degree가 1인 그래프에서 cycle에 속하지 않은 노드의 개수를 구하는 문제이다.

문제 풀이

• component를 생각하여 방문하지 않은 정점마다 dfs를 돌리면서 cycle을 체크하면 된다. cycle체크는 visited벡터를 0/1/-1(현재 스택에 존재할 때)로 나눠서 -1인 노드를 탐색할 때 cycle이 발견되었다고 처리했다.

소스코드

#include<cstdio>
#include<vector>
#include<stack>
using namespace std;
typedef vector<int> vi;

int main()
{
	int t, n;
	vi res;
	scanf("%d", &t);
	while(t--){
		scanf("%d", &n);
		int cidx=0, gidx=1;
		vi g(n), visited(n, 0), group(n, 0);
		for(int i=0;i<n;i++){
			int t;
			scanf("%d", &t);
			g[i]=--t;
		}

		while(cidx!=n){
			if(visited[cidx]!=0){
				cidx++;
				continue;
			}
			stack<int> st;
			st.push(cidx);
			visited[cidx]=-1;
			while(!st.empty()){
				int next=g[st.top()];
				if(visited[next]==0){
					st.push(next);
					visited[next]=-1;
				}
				else if(visited[next]==-1){
					while(st.top()!=next){
						group[st.top()]=gidx;
						visited[st.top()]=1;
						st.pop();
					}
					group[next]=gidx;
					visited[next]=1;
					st.pop();
				}
				else{
					while(!st.empty()){
						visited[st.top()]=1;
						st.pop();
					}
				}
			}
			cidx++;
		}
		gidx++;
		int nogcnt=0;
		for(int i=0;i<n;i++) if(group[i]==0) nogcnt++;
		res.push_back(nogcnt);
	}
	for(int i=0;i<res.size();i++) printf("%d\n", res[i]);
}

풀고나서

• cidx를 사용하지 않고 int isempty(vi& visited)라는 함수를 따로 만들어서 components처리하는 두 번째 while문을 while(isempty(visited)!=-1)로 돌렸었는데 이것때문에 시간초과가 나는 것을 어디서 무한루프가 도나 착각했었다.
  priority queue를 쓸 방법을 생각하다가 그냥 인덱스로 while문을 돌리면서 visited의 값을 처음에 확인하면 된다는 것을 깨달았다. 탐색 구현할 때마다 헷갈리지 않게 적어놔야겠다.

• component 시작점을 찾을 때는 그냥 인덱스로 visited 체크하면서 돌리면 된다