题目链接：http://www.codechef.com/JAN14/problems/SEAGRP
【题意】
给n个点,m条边的无向图，判断是否有一种删边方案使得每个点的度恰好为1.
【分析】
从结论入手，每个点的度恰好为1，那么就意味着每个点只能连接一个点，这样问题就转化为图中的点能否刚好两两配对。
对于奇数个点肯定是不行的，因为一定存在一个点不存在与之配对的点。
如果点是偶数，那么就要求这个图的最大匹配，看匹配树是否为点数的一半。
求匹配的方法和二分图类似，不断找增广路更新匹配数就好了。
【代码】
第一次手写增广路代码~写的时候忘记判断增广路是否重点了于是WA了，还好后来想到了。
#include <stdio.h>
#include <string.h>
#include <cmath>
#include <iostream>
#include<algorithm>
using namespace std;
int n,m;
int map[][];
int match[][];
int du[];
int path[];
bool ifv[];
int be;
bool dfs(int i,int k)
{
if ((k&) && !du[i] )
{
int t=k-;
while (t>=)
{
if (match[i][path[t]]==) {++du[i];++du[path[t]];}
else {--du[i];--du[path[t]];}
match[i][path[t]]=!match[i][path[t]];
match[path[t]][i]=!match[path[t]][i];
i=path[t];
--t;
}
return true;
}
for (int j=;j<=n;++j)
{
if (map[i][j]==-) continue;
if (match[i][j]!=(k&) ) continue;
if (ifv[j]) continue;
path[k]=i;
ifv[j]=true;
if (dfs(j,k+)) return true;
}
return false;
}
int main()
{
int T;
scanf("%d",&T);
while (T--)
{
memset(map,-,sizeof map);
memset(match,,sizeof match);
memset(du,,sizeof du);
scanf("%d%d",&n,&m);
for (int i=;i<m;++i)
{
int a,b;
scanf("%d%d",&a,&b);
map[a][b]=map[b][a]=;
}
if (n&) puts("NO");
else
{
int ans=;
for (int i=;i<=n;++i)
{
memset(ifv,,sizeof ifv);
ifv[i]=true;
if (!du[i] && dfs(i,)) ++ans;
}
if (ans==n/) puts("YES"); else puts("NO");
}
}
}