HDU 3081 Marriage Match II (헝가리 알고리즘 + 검색 집합)

/*
WA，       
  ：2*n   ，n   ，n   ，m              ，    f   。        ，                      ，       。            ，     。       。
  ：      +    
              ，       n，     。     ，        ，                   。             ，             。
*/

#include <iostream>
#define re(i, n) for(int i = 0; i < n; ++ i)
using namespace std;

const int nMax = 105;
int p[nMax];
int link[nMax];
int useif[nMax];
int map[nMax][nMax];
//int fhash[nMax][nMax];
int T, n, m, f;

int find(int x)//   
{
	return p[x] == x ? x : p[x] = find(p[x]);
}

int getPath(int t)//      
{
	re(i, n)
	{
		if(!useif[i] && map[t][i])
		{
			useif[i] = 1;
			if(link[i] == -1 || getPath(link[i]))
			{
				link[i] = t;
				return 1;
			}
		}
	}
	return 0;
}

int getNum()//     ，          O(N^3)
{
	int sum = 0;
	memset(link, -1, sizeof(link));
	re(i, n)
	{
		memset(useif, 0, sizeof(useif));
		sum += getPath(i);
	}
	if(sum == n)
		re(i, n)
		{
			map[link[i]][i] = 0;
		}
	return sum;
}

int main()
{
	//freopen("f://data.in", "r", stdin);
	scanf("%d", &T);
	while(T --)
	{
		scanf("%d %d %d", &n, &m, &f);
		int a, b;
		re(i, m)
		{
			scanf("%d %d", &a, &b);
			-- a;
			-- b;
			map[a][b] = 1;
		}
		re(i, n)
			p[i] = i;
		re(i, f)
		{
			scanf("%d %d", &a, &b);
			-- a;
			-- b;
			if(find(a) != find(b))
				p[a] = find(b);
		}
		/*
		re(i, n) re(j, n)//      ，      re(j, m)，     
		{
			if(map[i][j])
			{
				map[find(i)][find(j)] = 1;
			}
		}*/
		re(i, n)//        ，  i j    ， j k   ， i k    
		{
			int si = find(i);
			re(j, n)
				if(i != j && si == find(j))
					re(k, n)
					if(map[j][k])
						map[i][k] = 1;
		}
		//memset(fhash, 0, sizeof(fhash));
		int ans = 0;
		while(getNum() == n) ans ++;
		printf("%d
",ans);
	}
	return 0;
}