hdu 3081 二分图最大匹配

利用并查集建好图后：不断地求最大匹配、删除匹配边直到最大匹配不够n。
  1 #include <algorithm>
  2 #include <iostream>
  3 #include <cstring>
  4 #include <cstdio>
  5 using namespace std;
  6 
  7 const int N = 101;
  8 bool mp[N][N];
  9 int mark[N];
 10 bool visit[N];
 11 int fa[N];
 12 int n, m, f;
 13 
 14 struct Edge 
 15 {
 16     int from, to;
 17 } edge[N * N];
 18 
 19 int findf( int x )
 20 {
 21     if ( fa[x] != x ) fa[x] = findf(fa[x]);
 22     return fa[x];
 23 }
 24 
 25 void union_set( int x, int y )
 26 {
 27     x = findf(x), y = findf(y);
 28     if ( x != y )
 29     {
 30         fa[x] = y;
 31     }
 32 }
 33 
 34 int dfs( int u )
 35 {
 36     for ( int i = 1; i <= n; i++ )
 37     {
 38         if ( !visit[i] && mp[u][i] )
 39         {
 40             visit[i] = 1;
 41             if ( mark[i] == -1 || dfs(mark[i]) )
 42             {
 43                 mark[i] = u;
 44                 return 1;
 45             }
 46         }
 47     }
 48     return 0;
 49 }
 50 
 51 int hunagry()
 52 {
 53     int res = 0;
 54     memset( mark, -1, sizeof(mark) );
 55     for ( int i = 1; i <= n; i++ )
 56     {
 57         memset( visit, 0, sizeof(visit) );
 58         res += dfs(i);
 59     }
 60     return res;
 61 }
 62 
 63 void deleteEdge()
 64 {
 65     for ( int i = 1; i <= n; i++ )
 66     {
 67         mp[mark[i]][i] = 0;
 68     }
 69 }
 70 
 71 int main ()
 72 {
 73     int t;
 74     scanf("%d", &t);
 75     while ( t-- )
 76     {
 77         scanf("%d%d%d", &n, &m, &f);
 78         for ( int i = 1; i <= m; i++ ) scanf("%d%d", &edge[i].from, &edge[i].to);
 79         memset( mp, 0, sizeof(mp) );
 80         for ( int i = 1; i <= n; i++ ) fa[i] = i;
 81         for ( int i = 1; i <= f; i++ )
 82         {
 83             int p, q;
 84             scanf("%d%d", &p, &q);
 85             union_set( p, q );
 86         }
 87         for ( int i = 1; i <= m; i++ )
 88         {
 89             mp[findf(edge[i].from)][edge[i].to] = 1;
 90         }
 91         for ( int i = 1; i <= n; i++ )
 92         {
 93             int o = findf(i);
 94             if ( o == i ) continue;
 95             for ( int j = 1; j <= n; j++ )
 96             {
 97                 mp[i][j] = mp[o][j];
 98             }
 99         }
100         int ans = 0;
101         while ( hunagry() == n )
102         {
103             ans++;
104             deleteEdge();
105         }
106         printf("%d
", ans);
107     }
108     return 0;
109 }