PKU 1422. Air Raid. AC get!

#include <stdio.h> int found[1001][1001], checked[1001], followed[1001], inters; int DFS(int node) { int i, j; for (i = 1; i <= inters; i++) { if (found[node][i] != 0 && checked[i] == 0) { checked[i] = 1; j = followed[i]; followed[i] = node; if (j == 0 || DFS(j)) { return 1; } else { followed[i] = j; } } } return 0; } int main() { int cases, streets, start, end, sum, i, j, k; while (~scanf("%d", &cases)) { while (cases--) { scanf("%d%d", &inters, &streets); while (streets--) { scanf("%d%d", &start, &end); found[start][end] = 1; } sum = 0; for (i = 1; i <= inters; i++) { for (j = 0; j <= inters; j++) { checked[j] = 0; } if (DFS(i) != 0) { sum++; } } printf("%d\n", inters - sum); for (i = 0; i <= inters; i++) { for(j = 0; j <= inters; j++) { found[i][j] = 0; } checked[i] = 0; followed[i] = 0; } } } return 0; }<SPAN id=tx_marker_caret></SPAN>

이쯔어 뉴 솔루션!

원리는 예전과 같아요~

다만 구현방식을 2개의 행렬에서 1개의 입력행렬과, 추적을 위한 checked(방문했나, 가능하나)와 followed(이 노드가 널 가르킨다)

의 2개 배열을 이용해 간략화 시켰을 뿐입니다.

처리과정과 결과 완전히 동일합니다.

-_-...

왜 전에껀 WA일까?