graphdegree.cpp

求图的顶点连通度算法。方法就是先对源和汇做枚举

＃i nclude <cstdio>
＃i nclude <cstring>
＃i nclude <algorithm>
＃i nclude <queue>
using namespace std;

const int MAX = 64;
const int N_MAX = 128;
const int INF = 200000000;

class Network {
private:
        int size;
        int prev[N_MAX];
        bool augmentable(int, int);
public:
        int cap[N_MAX][N_MAX];
        void clear(int);
        int maxFlow(int, int);
};
void Network::clear(int n) {
        memset(cap, 0, sizeof(cap));
        size = n;
}
bool Network::augmentable(int s, int t) {
        queue<int> queue;
        memset(prev, -1, sizeof(prev));
        prev[s] = s;
        queue.push(s);
        while(!queue.empty()) {
                int p = queue.front(), i;
                queue.pop();
                for(i = 0; i < size; i++) {
                        if(cap[p][i] > 0 && prev[i] == -1) {
                                prev[i] = p;
                                if(i == t) {
                                        return true;
                                } else {
                                        queue.push(i);
                                }
                        }
                }
        }
        return false;
}
int Network::maxFlow(int s, int t) {
        int flow = 0, i;
        while(augmentable(s, t)) {
                int extend = INF;
                for(i = t; i != s; i = prev[i]) {
                        if(extend > cap[prev[i]][i]) {
                                extend = cap[prev[i]][i];
                        }
                }
                for(i = t; i != s; i = prev[i]) {
                        cap[prev[i]][i] -= extend;
                        cap[i][prev[i]] += extend;
                }
                flow += extend;
        }
        return flow;
}

int s, t, n;

bool connect(int[][MAX]);
inline int in(int);
inline int out(int);

int main()
{
        Network net;
        int map[MAX][MAX];
        int m, i, j, T = 0;

        while(scanf("%d %d", &n, &m) == 2) {
                if(T != 0) putchar('\n');
                T++;
                memset(map, 0, sizeof(map));
                int edge = 0;
                for(i = 0; i < m; i++) {
                        int a, b;
                        scanf("\n(%d,%d)", &a, &b);
                        if(map[a][b] == 0) edge++;
                        map[a][b]++, map[b][a]++;
                }
                if(edge == n*(n-1)/2) printf("%d", n);
                else if(!connect(map)) printf("0");
                else {
                        int f = INF;
                        for(s = 0; s < n; s++) {
                                for(t = s+1; t < n; t++) {
                                        net.clear(2*n-2);
                                        for(i = 0; i < n; i++) {
                                                for(j = 0; j < n; j++) {
                                                        if(i != j) {
                                                                net.cap[in(i)][out(j)] = 
                                                                        net.cap[in(j)][out(i)] = map[i][j];
                                                        } else if(i != s && i != t) {
                                                                net.cap[in(i)][out(i)] = 
                                                                        net.cap[out(i)][in(i)] = 1;
                                                        }
                                                }
                                        }
                                        f = min(f, net.maxFlow(0, 2*n-3));
                                }
                        }
                        printf("%d", f);
                }
        }

        return 0;
}

bool connect(int map[][MAX])
{
        bool visit[MAX] = { false };
        int i, j;
        queue<int> queue;
        queue.push(0); visit[0] = true;
        while(!queue.empty()) {
                int t = queue.front(); queue.pop();
                for(j = 0; j < n; j++) {
                        if(map[j][t] != 0 && !visit[j]) {
                                visit[j] = true;
                                queue.push(j);
                        }
                }
        }
        for(i = 0; i < n; i++) {
                if(!visit[i]) return false;
        }
        return true;
}
inline int in(int m)
{
        if(m == s) return 0;
        if(m == t) return 2*n-3;
        int c = 0;
        if(m > s) c++;
        if(m > t) c++;
        return 2 * (m-c) + 1;
}
inline int out(int m)
{
        if(m == s || m == t) return in(m);
        else return in(m) + 1;
}