题意：有n个学生，每一个学生都和一些人有关系，如今要你找出最大的人数。使得这些人之间没关系

思路：求最大独立集，最大独立集=点数-最大匹配数

分析：建图时应该是一边是男生的点，一边是女生的点连边。可是题目中没说性别的问题。仅仅能将每一个点拆成两个点。一个当作是男的点，一个当作是女的点了，然后连边.因为关系是相互的。这样就造成了边的反复。也就是边集是刚才的二倍，从而导致了最大匹配变成了原本的二倍。因此，此时最大独立集=点数-最大匹配数/2.

#include
     
      #include
      
       int n,edge[510][510],link[510],used[510];int dfs(int pos){    int i;    for(i=0;i
      
     

版权声明：本文博主原创文章，博客，未经同意不得转载。