题目描述：

给你一个无向图，问你最少删掉几个点，使这个图成不连通。

解题报告：

概念

(1)一个具有 N 个顶点的图，在去掉任意 k-1 个顶点后 (1<=K<=N) 所得的子图仍连通，

　　而去掉 K 个顶点后的图不连通则称 G 是连通的， K 称作图 G 的点连通度，记作 K(G) 试设计

(2)相应地如果至少去掉 K 条边使这个图不连通，则 K 成为图的边连通度

边连通度：

　　为每条边赋权值为1,然后求确定一点作为源点，枚举此点外的每个点作为汇点求最大流。

　　也可以用stoer_wagner算法求得无向图的最小割

点连通度：

　　求一个给定的无向图的点连通度，可以转换为求边连通度，怎么转换就如下所示：

将点连通度转化为边连通度时怎么建图呢：

1 ．构造一个网络 N

若 G 为无向图：

    (1) 原 G 图中的每个顶点 v 变成 N 网中的两个顶点 v' 和 v" ，顶点 v' 至 v" 有一条弧（有向边）连接，弧容量为 1;

    (2) 原 G 图中的每条边  e ＝ uv ，在 N 网中有两条弧 e’= u"v',e"=v"u' 与之对应， e' 弧容量为 ∞ ，  e" 弧容量为 ∞

    (3)A” 为源顶点， B' 为汇顶点

     注意：弧是有向边

若 G 为有向图：

    (1) 原 G 图中的每个顶点变成 N 网中的两个顶点 v’ 和 v” ，顶点 v' 至 v” 有一条弧连接，弧容量为 1

    (2) 原 G 图中的每条弧  e ＝ uv 变成一条有向轨 u'u"v'v" ，其中轨上的弧 u"v' 的容量为 ∞;

    (3)A” 为源顶点， B' 为汇顶点

2 ．指定一个源点 A" ，枚举汇点B'，求 A" 到 B' 的最大流 F

代码如下：

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;
#define Max 0x1fffffff
#define size 200
struct edge{int from, to, val, next;}e[140000];
int v[size], que[size], dis[size], cnt, cur[size], ee[20000][2];
void insert(int from, int to, int va)
{
    e[cnt].from = from, e[cnt].to = to; e[cnt].val = va;
    e[cnt].next = v[from];v[from] = cnt++;
    e[cnt].from = to, e[cnt].to = from; e[cnt].val = 0;
    e[cnt].next = v[to];v[to] = cnt++;
}
bool bfs(int n, int s, int t)
{
    int head, tail, id;
    head = tail = 0; que[tail++] = s;
    memset(dis, -1, sizeof(int) * n);dis[s] = 0;
    while(head < tail) // bfs,得到顶点i的距s的最短距离dis[i]
        for(id = v[que[head++]]; id != -1; id = e[id].next)
            if (e[id].val > 0 && dis[e[id].to] == -1)
            {
                dis[e[id].to] = dis[e[id].from] + 1;
                que[tail++] = e[id].to;
                if (e[id].to == t) return true;
            }
    return false;
}
int Dinic(int n, int s, int t)
{
    int maxflow = 0, tmp, i;
    while(bfs(n, s, t))
    {
        int u = s, tail = 0;
        for(i = 0; i < n; i++) cur[i] = v[i];
        while(cur[s] != -1)
            if (u != t && cur[u] != -1 && e[cur[u]].val > 0 && dis[u] != -1 && dis[u] + 1 == dis[e[cur[u]].to])
            {que[tail++] = cur[u]; u = e[cur[u]].to;}
            else if (u == t)
            {
                for(tmp = Max, i = tail - 1; i >= 0; i--) tmp = min(tmp, e[que[i]].val);
                for(maxflow += tmp, i = tail - 1; i >= 0; i--)
                {
                    e[que[i]].val -= tmp;
                    e[que[i] ^ 1].val += tmp;
                    if (e[que[i]].val == 0) tail = i;
                }
                u = e[que[tail]].from;
            }
            else
            {
                while(tail > 0 && u != s && cur[u] == -1) u = e[que[--tail]].from;
                cur[u] = e[cur[u]].next;
            }
    }
    return maxflow;
}
int n ,m;
int main()
{
    while(scanf("%d%d", &n, &m) != EOF)
    {
        for(int i = 0; i < m; i++)
        {
            while(getchar() != '(');
            scanf("%d,%d)", &ee[i][0], &ee[i][1]);
        }
        int s = n, ans = Max;
        for(int t = 1; t < n; t++)
        {
            memset(v, -1, sizeof(int) * (n + n)); cnt = 0;
            for(int i = 0; i < n; i++) insert(i, i + n, 1);
            for(int i = 0; i < m; i++)
                insert(ee[i][0] + n, ee[i][1], Max), insert(ee[i][1] + n, ee[i][0], Max);
            ans = min(ans, Dinic(n + n, s, t));
        }
        if (ans >= Max) ans = n;
        printf("%d\n", ans);
    }
    return 0;
}