题目描述

有n个女孩和男孩在玩游戏，游戏规则是一个女孩找一个男孩当她男朋友玩过家家。当每个女孩都找到男朋友后一轮进下一轮游戏，在之后的游戏中女孩的男朋友不能与之前的男朋友相同，如果有女孩子找不到男朋友则游戏结束。

女孩寻找男孩满足如下两个要求:
如果男孩b和女孩g没有吵架过，那么女孩g会选男孩b做男朋友。
如果女孩og和女孩g是朋友(此时的g为上面的g相同),那么女孩og也可以选男孩b做男朋友。女孩之间的友谊可以传递。
问: 游戏最多能玩几轮?

样例

输入
1       //只有一组案例
4 5 2       //n m f
1 1     //g b 先输入女孩，再输入男孩
2 3
3 2
4 2
4 4
1 4     //g1 g2 是朋友关系
2 3
输出
2

基本思路

1 男女配对，很显然是二分图的匹配问题
2 因为女生有密切关系需要处理，所以可以想到，要么在女生间建边，然后再暴力建男女之间的边
要么用并查集来维护，感觉并查集会方便些。
3 用并查集将有关系的女生放入到一个集合里面
4 然后考虑构造图，这里我分为两部进行。首先，第一个大循环中，找到每个女生的”祖先“，如果这个女生
和某个男生有边，那么祖先和那个男生也应该有边。第二个大循环，找到每个女生的”祖先“，如果祖先和某个
男生有边，那么这个女生和那个男生也应该有边。
5 开始用模板循环，注意到的是，每次如果能成功匹配，那么要删去女生和她匹配的男生之间的边。

C++ 代码

#include <bits/stdc++.h>
using namespace std;
const int N = 2010;
int g[N][N];
int p[N],match[N];
int n,m,f;
bool st[N];

int find(int x)
{
    if(x != p[x])
    {
        p[x] = find(p[x]);
    }
    return p[x];
}

void init()
{
    memset(g,0,sizeof g);
    memset(st,0,sizeof st);
    memset(match,0,sizeof match);
    for(int i = 1;i <= n;i++)
    {
        p[i] = i;
    }
}

void build()
{
    for(int i = 1;i <= n;i++)
    {
        int pa = find(i);
        for(int j = n + 1;j <= 2 * n;j++)
        {
            if(g[i][j] == 1)
            {
                g[pa][j] = 1;
            }
        }
    }
    for(int i = 1;i <= n;i++)
    {
        int pa = find(i);
        for(int j = n + 1;j <= 2 * n;j++)
        {
            if(g[pa][j] == 1)
            {
                g[i][j] = 1;
            }
        }
    }
}

bool hungarian(int u)
{
    for(int i = n + 1;i <= 2 * n;i++)
    {
        if(!st[i] && g[u][i])
        {
            st[i] = true;
            if(match[i] == 0 || hungarian(match[i]))
            {
                match[i] = u;
                return true;
            }
        }
    }
    return false;
}

bool dfs()
{
    int res = 0;
    memset(match,0,sizeof match);
    for(int i = 1;i <= n;i++)
    {
        memset(st,0,sizeof st);
        if(hungarian(i))
        {
            res++;
        }
    }
    if(res == n)
    {
        return true;
    }
    else
    {
        return false;
    }
}

int solve()
{
    int ans = 0;
    while(dfs())
    {
        ans++;
        for(int i = n + 1;i <= 2 * n;i++)
        {
            g[match[i]][i] = 0;
        }

    }
    return ans;
}

int main()
{
    int t;
    cin >> t;
    while(t--)
    {

        cin >> n >> m >> f;
        init();
        while(m--)
        {
            int a,b;
            cin >> a >> b;
            b = b + n;
            g[a][b] = g[b][a] = true;
        }
        while(f--)
        {
            int a,b;
            cin >> a >> b;
            int pa = find(a),pb = find(b);
            if(pa != pb)
            {
                p[pa] = pb;
            }
        }
        build();
        cout << solve() << endl;
    }
}