题目链接：http://poj.org/problem?id=1966
题目大意：

题意：求一个无向图的点连通度。点联通度是指，一张图最少删掉几个点使该图不连通；若本身是非连通图，则点连通度为0。

思路：无向图的点连通度可以转化为最大流解决。方法是：1.任意选择一个点作为源点；2.枚举所有与该点间没有边的点作为汇点；3.将每个点拆为入点和出点，入点到出点建一条流量为1的边；4.原本有边关系的两点，建流量为正无穷的双向边；5.每次跑出最大流，其中最小值即点连通度，若最小值为正无穷，则说明点连通度为|顶点数|。

注意：源点为出点， 汇点为入点。

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
const int maxn = 1e5 + 10;
const int INF = 0x3f3f3f3f;
int cas = 1, T;
int d[maxn], cur[maxn], start, tend;
struct node
{
    int to, cap, next;

} edge[maxn << 1];

int head[maxn];
bool vis[maxn];
int cnt;

void addedge(int start, int to, int cap)
{
    edge[cnt].to = to;
    edge[cnt].cap = cap;
    edge[cnt].next = head[start];
    head[start] = cnt++;
}

void add(int start, int to, int cap){

    //cout<<start<<" "<<to<<" "<<cap<<endl;
    addedge(start, to, cap);
    addedge(to, start, 0);
}

bool BFS()
{
    //memset(vis,false,sizeof(vis));
    memset(d, -1, sizeof(d));
    int Q[maxn * 2];
    int Thead, Ttail;
    Thead = Ttail = 0;
    Q[Ttail++] = start;;
    d[start] = 0;
    //vis[start]=1;
    while (Thead<Ttail)
    {
        int x = Q[Thead];
        if (x == tend)
            return true;
        for (int i = head[x]; i != -1; i = edge[i].next)
        {
            int temp = edge[i].to;
            if (d[temp] == -1 && edge[i].cap>0)//没有标记,且可行流大于0
            {
                //vis[temp.to]=true;
                d[temp] = d[x] + 1;
                Q[Ttail++] = temp;
            }
        }
        Thead++;
    }
    return false;//汇点是否成功标号,也就是说是否找到增广路
}
int DFS(int x, int cap)
{
    if (x == tend)
        return cap;
    //vis[start]=true;
    int flow = 0, f;
    for (int i = head[x]; i != -1; i = edge[i].next)
    {
        int temp = edge[i].to;
        //if(temp.cap<=0||vis[temp.to])continue;
        if (d[temp] == d[x] + 1 && edge[i].cap)
        {
            f = DFS(temp, min(cap - flow, edge[i].cap));
            edge[i].cap -= f;
            edge[i ^ 1].cap += f;
            flow += f;
            if (flow == cap)
                break;
        }
    }
    if (!flow)
        d[x] = -2;//防止重搜
    return flow;
}
int maxflow()
{
    int flow = 0, f;
    while (BFS())
    {
        //memset(vis,false,sizeof(vis));
        while ((f = DFS(start, INF))>0)
            flow += f;
    }
    return flow;
}

int G[55][55];
int main()
{
    int n, m, u, v;
    while(~scanf("%d%d", &n, &m)){
        memset(G, 0, sizeof(G));
        for(int i=1; i<=m; i++){
            scanf(" (%d,%d)", &u, &v);
            G[u][v]=G[v][u]=1;
        }
        int ans=INF;
        start=n;//0为起点， 出点为n
        for(int i=1; i<n; i++){
            if(!G[0][i]){

                tend=i;//枚举终点
                cnt = 0;
                memset(head, -1, sizeof(head));
                for(int k=0; k<n; k++){
                    add(k, k+n, 1);
                }
                for(int k=0; k<n; k++){
                    for(int j=k+1; j<n; j++){
                        if(G[k][j]){//连边
                            add(k+n, j, INF);
                            add(j+n, k, INF);
                        }
                    }
                }
                ans=min(ans, maxflow());
            }
        }
        if(ans==INF){
            ans=n;
        }
        printf("%d\n", ans);
    }

    return 0;
}