学步园

最小顶点覆盖

第一次用vector

#include<stdio.h>
#include<vector>
#include<string.h>
using std::vector;
vector<int>map[1510];
int link[1510],mark[1510],n,m;
int find(int i)
{
    int j,k;
    for(j=0;j<map[i].size();j++)
    {
        if(mark[k=map[i][j]]==0)
        {
            mark[k]=1;
            if(link[k]==0||find(link[k])==1)
            {
                link[k]=i;
                return 1;
            }
        }
    }
    return 0;
}
int main()
{
    int i,sum,j,x,y,z;
    while(scanf("%d",&n)!=-1)
    {
        memset(map,0,sizeof(map));
        memset(link,0,sizeof(link));
        for(i=1;i<=n;i++)
        {
            scanf("%d:(%d)",&x,&z);
            for(j=1;j<=z;j++)
            {
                scanf("%d",&y);
                 map[x].push_back(y);
                 map[y].push_back(x);
            }
        }
            sum=0;
            for(i=0;i<n;i++)
            {
                    memset(mark,0,sizeof(mark));
                    sum=sum+find(i);
            }
            
                    printf("%d\n",sum/2);
                    for(i=0;i<n;i++)
                    map[i].clear();
    }
    return 0;
}