题目链接

<h1>题目描述</h1>

给定一张无向图，求让这张无向图不连通应删去的点的最小个数。

<h1>解题报告</h1>

首先发现这很像割的定义，只不过由边转化为了点。
那我们不妨拆点来对边进行限制：其中对于每个点 $v$ 拆成 $v$ 和 $v'$ ，然后我们在这两个点之间连一条容量为 $1$ 的边，然后原图边容量为 $INF$ ，用最大流最小割定理求解即可。
但是我们发现题目里没有给出源点和汇点，直接的想法是枚举，但是我们其实可以固定一个源点，只枚举汇点就可以了，最后对于每一次的最大流都取个最小值就可以了。

<h1>代码</h1>

#include <algorithm>
#include <iostream>
#include <cstring>
//#include <climits>
#define INT_MAX 2147483645
#include <cstdio>
#include <vector>
#include <cstdlib>
#include <ctime>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>

#define Re register
#define LL long long
#define U unsigned
#define FOR(i,a,b) for(Re int i = a;i <= b;++i)
#define ROF(i,a,b) for(Re int i = a;i >= b;--i)
#define SFOR(i,a,b,c) for(Re int i = a;i <= b;i+=c)
#define SROF(i,a,b,c) for(Re int i = a;i >= b;i-=c)
#define CLR(i,a) memset(i,a,sizeof(i))
#define BR printf("--------------------n")
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl
#define int LL
const int MAXN = 1000+5;
const int MAXM = 20000+5;

struct Node{
    struct Edge first,cur;
    int level,num;
}node[MAXN];

struct Edge{
    Node s,t;
    Edge next,rev;
    int cap,flow;
}pool[MAXM<<1],*frog = pool;

Edge New(Node s,Node *t,int cap){
    Edge *ret = ++frog;
    *ret = (Edge){s,t,s->first,NULL,cap,0};
    return ret;
}

inline void add(int u,int v,int cap){
    // printf("%d %d %dn",u,v,cap);
    node[u].first = New(&node[u],&node[v],cap);
    node[v].first = New(&node[v],&node[u],0);
    node[u].first->rev = node[v].first;
    node[v].first->rev = node[u].first;
}

int S,T,N;

bool bfs(Node s,Node t){
    FOR(i,0,N){
        node[i].cur = node[i].first;
        node[i].level = 0;node[i].num = i;
    }
    std::queue<Node *> q;q.push(s);
    s->level = 1;
    while(!q.empty()){
        Node *v = q.front();q.pop();
        for(Edge *e = v->first;e;e = e->next){
            if(e->flow < e->cap && !e->t->level){
                e->t->level = v->level + 1;
                if(e->t == t) return true;
                q.push(e->t);
            }
        }
    }
    return false;
}

int dfs(Node v,Node t,int limit=INT_MAX){
    if(v == t) return limit;
    int flow;
    for(Edge *&e = v->cur;e;e = e->next){
        if(e->flow < e->cap && e->t->level == v->level + 1){
            if((flow = dfs(e->t,t,std::min(limit,e->cap-e->flow)))){
                e->flow += flow;
                e->rev->flow -= flow;
                return flow;
            }
        }
    }
    return 0;
}

int dinic(){
    int flow,ans=0;
    for(Edge *e = pool;e != frog+1;e++) e->flow = 0;
    while(bfs(&node[S],&node[T])){
        while((flow = dfs(&node[S],&node[T]))){
            ans += flow;
        }
    }
    return ans;
}

inline void init(){
    CLR(node,0);frog = pool;
}

int n,m;

inline void Solve(){
    init();
    FOR(i,1,m){
        int u,v;
        scanf(" (%lld,%lld)",&u,&v);//u++;v++;
        add(u+n,v,INT_MAX);add(v+n,u,INT_MAX);
    }
    FOR(i,0,n) add(i,i+n,1);
    S = n;N = (n<<1);
    int ans = n;
    FOR(i,1,n-1){
        T = i;//DEBUG(ans);
        ans = std::min(ans,dinic());
    }
    printf("%lldn",ans);
}
/*
1 2
1 3
2 3
*/

signed main(){
    while(~scanf("%lld%lld",&n,&m)) Solve();
    return 0;
}
/*
1 4 1
2 5 1
3 6 1
4 2 100000000
5 1 100000000
4 3 100000000
6 1 100000000
5 3 100000000
6 2 100000000
*/