Vertex Cover

短命女 2022-06-10 11:06 185阅读 0赞

# Vertex Cover #

frog has a graph with n n vertices v(1),v(2),…,v(n) v(1),v(2),…,v(n) and m m edges (v(a1),v(b1)),(v(a2),v(b2)),…,(v(am),v(bm)) (v(a1),v(b1)),(v(a2),v(b2)),…,(v(am),v(bm)).

She would like to color some vertices so that each edge has at least one colored vertex.

Find the minimum number of colored vertices.

## Input ##

The input consists of multiple tests. For each test:

The first line contains 2 2 integers n,m n,m (2≤n≤500,1≤m≤n(n−1)2 2≤n≤500,1≤m≤n(n−1)2). Each of the following m m lines contains 2 2 integers ai,bi ai,bi (1≤ai,bi≤n,ai≠bi,min\{ ai,bi\}≤30 1≤ai,bi≤n,ai≠bi,min\{ai,bi\}≤30)

## Output ##

For each test, write 1 1 integer which denotes the minimum number of colored vertices.

## Sample Input ##

3 2
        1 2
        1 3
        6 5
        1 2
        1 3
        1 4
        2 5
        2 6

## Sample Output ##

1
        2

#include <cstdio>
    #include <vector>
    #include <cstring>
    using namespace std;
    vector<int>map[505];
    bool vis[505];
    int conn[505];
    bool dfs(int x)
    {
        for(int i=0; i<map[x].size(); i++)
        {
            int y=map[x][i];
            //printf("y=%d ",y);
            if(!vis[y])
            {
                vis[y]=true;
                if(conn[y]==0||dfs(conn[y]))
                {
                    conn[y]=x;
                    conn[x]=y;
                    return true;
                }
            }
        }
        return false;
    }
    int main()
    {
        int n,m;
        while(~scanf("%d %d",&n,&m))
        {
            memset(conn,0,sizeof(conn));
            memset(map,0,sizeof(map));
            for(int i=0; i<m; i++)
            {
                int a,b;
                scanf("%d %d",&a,&b);
                map[a].push_back(b);
                map[b].push_back(a);
            }
            int ans=0;
            for(int i=1; i<=n; i++)
            {
                if(!conn[i]){
                memset(vis,false,sizeof(vis));
                if(dfs(i))
                    ans++;
                }
            }
            printf("%d\n",ans);
        }
        return 0;
    }