NYOJ 239 月老的難題 (深度優先遍歷)

月老的難題

描述

月老准備給n個女孩與n個男孩牽紅線，成就一對對美好的姻緣。

現在，由於一些原因，部分男孩與女孩可能結成幸福的一家，部分可能不會結成幸福的家庭。

現在已知哪些男孩與哪些女孩如果結婚的話，可以結成幸福的家庭，月老准備促成盡可能多的幸福家庭，請你幫他找出最多可能促成的幸福家庭數量吧。

假設男孩們分別編號為1~n,女孩們也分別編號為1~n。

輸入

第一行是一個整數T,表示測試數據的組數(1<=T<=400)
每組測試數據的第一行有兩個整數n,K，其中男孩的人數與女孩的人數都是n。(n<=500,K<=10 000)
隨後的K行，每行有兩個整數i,j表示第i個男孩與第j個女孩有可能結成幸福的家庭。(1<=i,j<=n)

輸出

對每組測試數據，輸出最多可能促成的幸福家庭數量

樣例輸入

1
3 4
1 1
1 3
2 2
3 2

樣例輸出

2

題目分析:

我的做法是設兩個數組visBoy[],visGirl[],用來表示某個男孩或者女孩是否已經訪問了.

第一種情況,男孩沒有訪問,與他配對的女孩也沒有訪問,最簡單的情況,計數器加一;

第二種情況,男孩沒訪問,但與他配對的女孩已經訪問(與其他男孩配對),這時可以判斷一下與該女孩配對的男孩可不可以換一個女生,如果可以的話,計數器加一;

代碼如下:

/*************************************************************************
    > File Name: match_maker.c
    > Author: litingdong
    > Mail: [email protected] 
    > Created Time: 2014年05月23日 星期五 20時34分36秒
 ************************************************************************/

#include
#include
#include
#define MAXN  501
#define N    10001
int head[N];
struct EDGE
{
	int to,next;
}edge[N];
int m=0;
int visBoy[MAXN];
int visGirl[MAXN];
void add_edge(int u,int v)
{
edge[m].to=v;
edge[m].next=head[u];
head[u]=m++;
}
int dfs(int boy)
{
	int girl;
	int i;
	for(i=head[boy];i!=-1;i=edge[i].next)
	{
		girl=edge[i].to;
		if(!visBoy[girl])
		{
			visBoy[girl]=1;
			if(!visGirl[girl]||dfs(visGirl[girl]))
			{
				visGirl[girl]=boy;//存的是與她配對的男生的編號.
				return 1;
			}
		}
	}
	return 0;
}
int main()
{
	int t;
	scanf("%d",&t);
	while(t--)
	{
    memset(head,-1,sizeof(head));
	memset(visGirl,0,sizeof(visGirl));
	m=0;//極其關鍵,相當於初始化edge[N];
	int n,k;
	scanf("%d%d",&n,&k);
	int i;
	for(i=0;i