这个题有点坑,用邻接表存过不了,难受
#include<stdio.h>
#include<vector>
#include<cstring>
using namespace std;
const int N= 5001;
vector<int>v[N];
int match[N];
bool used[N];
int n;
int find(int u) {
int size=v[u].size();
for(int i=0; i<size; i++) {
int s=v[u][i];
if(!used[s]) {
used[s]=true;
if(match[s]==-1||find(s)) {
match[s]==u;
return 1;
}
}
}
return 0;
}
int main() {
int T;
scanf("%d",&T);
while(T--) {
int ans=0;
scanf("%d",&n);
for(int i=1; i<=3*n/2; i++)
{
int a,b;
scanf("%d%d",&a,&b);
v[a].push_back(b);
v[b].push_back(a);
}
memset(match,-1,sizeof(match));
for(int i=1; i<=n; i++) {
memset(used,false,sizeof(used));
if(find(i))
ans++;
}
printf("%d\n",ans/2);
}
}