PKU 1904. King's Quest. Wait for Server-_-

#include <iostream> #include <algorithm> const int SHIT = 3000; using namespace std; int iPrinceChoice[SHIT][SHIT], temp1[SHIT][SHIT] = {0}, temp2[SHIT][SHIT] = {0}; int iUserStack[SHIT], iTopOfStack, iChecker; int iPlayBoy[SHIT] = {0}, label[SHIT] = {0}; void DFS_1(int fuck); void DFS_2(int fuck); int main() { int i, j, k, n; int iPrincess[SHIT]; scanf("%d", &n); for (i = 1; i <= n; i++ ) { scanf("%d", &iPrinceChoice[i][0]); for (k = 1; k <= iPrinceChoice[i][0]; k++) { scanf("%d", &iPrinceChoice[i][k]); } } for (i = 1; i <= n; i++ ) { scanf("%d", &j); iPrincess[j] = i; } for (i = 1; i <= n; i++ ) { for (j = 1; j <= iPrinceChoice[i][0]; j++) { k = iPrincess[iPrinceChoice[i][j]]; temp1[i][0]++ ; temp1[i][temp1[i][0]] = k; temp2[k][0]++ ; temp2[k][temp2[k][0]] = i; } } for (i = 1; i <= n; i++) { if (iPlayBoy[i] == 0) { DFS_1(i); } } memset(iPlayBoy, 0, sizeof(iPlayBoy)); iChecker = 1; while (iTopOfStack>0) { if (iPlayBoy[iUserStack[iTopOfStack - 1]] == 0) { DFS_2(iUserStack[iTopOfStack - 1]); iChecker++; } iTopOfStack--; } for (i = 1; i <= n; i++) { iTopOfStack = 0; for (j = 1; j <= iPrinceChoice[i][0]; j++) { k = iPrincess[iPrinceChoice[i][j]]; if (label[k] == label[i]) { iUserStack[iTopOfStack++] = iPrinceChoice[i][j]; } } sort(iUserStack, iUserStack + iTopOfStack); printf("%d", iTopOfStack); for (j = 0; j < iTopOfStack; j++) { printf(" %d", iUserStack[j]); } printf("\n"); } } void DFS_1(int fuck) { iPlayBoy[fuck] = -1; for (int j = 1; j <= temp1[fuck][0]; j++) { if (iPlayBoy[temp1[fuck][j]] == 0) { DFS_1(temp1[fuck][j]); } } iUserStack[iTopOfStack++] = fuck; } void DFS_2(int fuck) { iPlayBoy[fuck] = -1; label[fuck] = iChecker; for (int j = 1; j <= temp2[fuck][0]; j++) { if (iPlayBoy[temp2[fuck][j]] == 0) { DFS_2(temp2[fuck][j]); } } }

....

빌어먹을 -_-

스'뽜'킹군..

나 이거 설명할 자신 없어...

-_-;;;

대략적으로 Mr.K가 제시한 솔루션과 동일하다고 보면 됩니다.

(리턴군의 지적대로, 제가 말한 DFS를 이용한게 Mr.K의 방법입니다.)

DFS를 두번이나 때리는 무식한 짓을 하긴 했습니다만...

일단 답이 제대로 나오고,

AC 받을 확률도 매우 높기 때문에 서버를 기-_-다리고 있습니다.

일단 scanf를 이용하여(서버에서 그리 권했으니깐요 ㅡ,.ㅡ;) 입력을 받고,

temp1과 temp2를 이용해 Mr.K가 그렸던 표를 2차원 배열로 구성합니다.

이걸 이용해 DFS로 강한 연결을 찾아내면 됩니다.

제가 백트래킹에 대해 얘기해놓고 DFS로 풀어놓은 이유가 뭔고 하니...

백트래킹을 이용한 재귀호출법으로 풀려면

3개의 set(C++ STL)을 써야 하는듸,

이 경우 TL이 당연히 날 수 밖에 없더군요 -_-;;;

이 STL을 이용한 방법을 C언어화 시켜놓고 나니 DFS를 이용한 풀이와 똑같군요.

STL을 이용한 풀이는 공주들과 왕자들, 중간 임시 set을 만든 후

이에 대해 가능한 모든 경우를 체크해서,

가능한 경우에만 해당 왕자의 set에 데이터를 추가하는 방식입니다.

뭐.. 일단은 이정도로...