Marriage Match II

                  给你n个男的n个女的，然后给你m中关系用a b来表示，表示女a愿意和男b结婚，然后给你k种关系用a b 表示，表示女a和女b是好朋友，如果a是b的朋友，那么a也愿意和b喜欢的男的结婚，b也愿意和a喜欢的男的结婚，然后所有女进行婚配，再拆散再一次进行婚配，这一次每个女的不能选之前选过的男的，问你最多可以进行多少轮婚配使得所有女的都能选到男的

题目思路：

                 首先我们考虑朋友之间的可以相互喜欢，所以我们很好想到用并查集来处理朋友的集合，然后再一次进行建图，对于最多进行的次数，我们可以循环进行二分匹配，每次匹配后把匹配的边删掉，然后在进行匹配，依次进行

AC代码：

#include<cstring>
#include<cstdio>

const int maxn = 105;

int link[maxn],pre[maxn];
bool vis[maxn],mp[maxn][maxn];
int n,m,k;


int get(int x){              //并查集处理朋友的集合
    if(pre[x]==-1)pre[x]=x;
    if(x!=pre[x]){
        pre[x]=get(pre[x]);
    }
    return pre[x];
}

void unio(int x,int y){
    if(x!=y)pre[x]=y;
}

bool dfs(int u){
    for(int i=1;i<=n;i++){
        if(!vis[i]&&mp[u][i]){
            vis[i]=true;
            if(link[i]==-1||dfs(link[i])){
                link[i]=u;
                return true;
            }
        }
    }
    return false;
}

void sove(){
    int ans = 0,num;
    do{
        memset(link,-1,sizeof(link));
        num = 0;
        for(int i=1;i<=n;i++){
            memset(vis,false,sizeof(vis));
            if(dfs(i))num++;
        }
        for(int i=1;i<=n;i++){
            if(link[i]!=-1){
                mp[link[i]][i]=false;     //将每次匹配的边删掉
            }
        }
        if(num==n)ans++;
    }while(num==n);               // 最大匹配为n说明每个女的都匹配到了
    printf("%d\n",ans);
}

int main()
{
    int t;scanf("%d",&t);
    while(t--){
        scanf("%d%d%d",&n,&m,&k);
        memset(mp,false,sizeof(mp));
        memset(pre,-1,sizeof(pre));
        while(m--){
            int a,b;scanf("%d%d",&a,&b);
            mp[a][b]=true;
        }
        while(k--){
            int u,v;scanf("%d%d",&u,&v);
            unio(get(u),get(v));
        }
        for(int i=1;i<=n;i++){
            int x = get(i);
            for(int j=1;j<=n;j++){
                if(get(j)==x&&j!=i){
                    for(int k=1;k<=n;k++){
                        if(mp[j][k])mp[i][k]=true;   //朋友之间的相互连边
                    }
                }
            }
        }
        sove();
    }
    return 0;
}