PKU 1422. Air Raid. AC get!

알 수 없는 사용자 2010. 6. 24. 10:19

#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일까?