Gym 101915D（最大团）

传送门

题面：

D. Largest Group

time limit per test

2.0 s

memory limit per test

64 MB

input

standard input

output

standard output

One day your university decided to run some statistics. They wanted to study friendship relations among boys and girls, and its effectiveness on their grades.

Strange thing about your university is that it has the exact same number of boys and girls. More formally, the university has P boys numbered from 1 to P, and P girls numbered from 1 to P.

We know that any pair of boys are surely friends, and any pair of girls are definitely friends. However, boys and girls are not always friends. To be precise, the university has a list of length N containing the friendship relations between girls and boys. the ith friendship relation is described by two integers bi and gi meaning that the boy number bi and girl number gi are friends.

One of the statistics your university is interested in, is the largest group of people (boys and girls) where any pair of them are friends. Can you write a program that would solve such a problem?

Input

The first line contains an integer T, the number of test cases.

Each test case starts with a line containing 2 space separated integers P and N denoting both the number of boys and girls at your university, and the number of friendship relations. (1 ≤ P ≤ 20), (0 ≤ N ≤ P2).

N lines follow. The ith line of them contains 2 space separated integers bi, gi describing a friendship relation.

Output

For each test case print a single line, containing a single integer, denoting the number of people in the largest group where any pair of people among them are friends.

Example

input

Copy

output

Copy

5
4

题意：

有p个男生和p个女生，男生和男生之间，女生和女生之间相互认识，现在男生女生之间有n个关系，每个关系代表男生a女生b是朋友，现在问你最多有多少个人可以互相成为朋友。

题目分析：

很显然，题目中就是要让我们求出这个二分图的最大团。

最大团的定义：对于一般图来说，团是一个顶点集合，且由该顶点集合诱导的子图是一个完全图，简单说，就是选出一些顶点，这些顶点两两之间都有边。最大团就是使得选出的这个顶点集合最大。

而二分图的最大团=补图的最大独立集。而最大独立集=点数-最小点覆盖。

知道上述定义套上匈牙利算法的板子即可。

代码：

#include <bits/stdc++.h>
#define maxn 50
using namespace std;
int g[maxn][maxn];
int linker[maxn];
bool used[maxn];
int p,n;
bool dfs(int u){//匈牙利算法
    for(int v=1;v<=p;v++){
        if(!g[u][v]&&!used[v]){//注意因为是最大团，因此需要算的是补集
            used[v]=true;
            if(linker[v]==-1||dfs(linker[v])){
                linker[v]=u;
                return true;
            }
        }
    }
    return false;
}
void hungry(){
    int res=0;
    memset(linker,-1,sizeof(linker));
    for(int u=1;u<=p;u++){
        memset(used,false,sizeof(used));
        if(dfs(u)) res++;
    }
    cout<<2*p-res<<endl;//最大独立集=点数-最小点覆盖（最大权匹配）
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--){
        scanf("%d%d",&p,&n);
        memset(g,0,sizeof(g));
        for(int i=0;i<n;i++){
            int a,b;
            scanf("%d%d",&a,&b);
            g[a][b]=1;
        }
        hungry();
    }
    return 0;
}