题目链接：?pid=2444
题意：判断所有人是否分为两个集合，，每个集合里的人互不相识。
思路：先判断是否为二分图，是的话求最大匹配，否则输出“No”。
代码：
;int n, k;int a, b;MAXM = 50010;//边struct Edge{int to;int next;}edge[MAXM];int head[MAXN], tot;void init(){tot = 0;memset(head,-1,sizeof(head));}void addedge(int u,int v){edge[tot].to = v;edge[tot].next = head[u];head[u] = tot++;}int linker[MAXN];bool used[MAXN];bool dfs(int u){for (int i = head[u]; i != -1; i = edge[i].next){int v = edge[i].to;if (!used[v]){used[v] = true;if (linker[v] == -1 || dfs(linker[v])){linker[v] = u;return true;}}}return false;}int hungary(){int ans = 0;memset(linker,-1,sizeof(linker));for (int u = 1; u <= n; u++){memset(used,false,sizeof(used));if (dfs(u)) ans++;}return ans;}int color[510];bool bfs(int u)//染色法 判断二分图{bool vis[510];memset(vis,false,sizeof(vis));for(int i=head[u];i != -1;i=edge[i].next){int v = edge[i].to;if (color[v] == -1){color[v] = !color[u];if (!bfs(v)) return false;}else if (color[v] == color[u])return false;}return true;}int main(){while (scanf(“%d%d”,&n,&k)!=EOF){init();while(k–){scanf(“%d%d”,&a,&b);addedge(a,b);addedge(b,a);}memset(color,-1,sizeof(color));//染色法 判断二分图color[1] = 1;if (!bfs(1)){puts(“No”);continue;}int ans = hungary();printf(“%d\n”,ans/2);}return 0;}
也许叔本华是对的，人与人的距离太远会寂寞到寒冷，
