学步园

习题7-3还无辜的WA着，以后有机会再debug出来

这个cutting chains难点完全在理解题意上啊

看到1-2 2-3这种东西，我第一反应是Editing a Book那道题。。导致我理解错误了很久。我以为打开以后就要立刻扣回去，并且最终形态一定要1-2-3-4...-n这样连着才可以，其实打开了之后放在一边不管就好了啊。。另外铁环们只要成串，顺序无所谓的啊

所以其实大概意思很简单的：随便打开几个环，然后看看最后能不能套成一串就可以了。那么基本思路就是枚举打开的环咯

另外sample input也是坑爹，最后一个case的1-2 2-1让我以为a-b和b-a这是不同的啊，但是根据board里的讨论，以及对铁环的常识，可以知道1-2和2-1根本tm没分别。。无视掉第二个就可以了啊

还有就是打开一定数量铁环后，能否连成串的判断：

1、没有环

2、打开的铁环足够把剩下的铁环串成串（没打开的铁环的连通量 <= 打开的铁环数 + 1；如果没有打开铁环，连通量 == 1）

3、不能有铁环的度大于2（一开始没想到啊。。感觉像是高中化学画同分异构体的时候加入了化合价要求一样），否则就会变成几条铁链交叉

最后再说一下一个小失误：

二进制枚举的时候，对1的判断应该用 if( s & (1 << i ))，是用了非零值均为true的机制。我一开始加了个 == 1，是对二进制枚举还不太熟。

Run Time: 0.855s

#define UVa  "7-4.818.cpp"

#include<cstring>
#include<cstdio>

using namespace std;


//Global Variables.
int n;
int kase = 0;
int G[20][20];
int circular_vis[20];
int connect_vis[20];
int step[2][4] = {{-1,0,1,0},{0,1,0,-1}};
/////

int circular(int cur, int prev) {
    for(int i = 0; i < n; i ++) if(i != cur && i != prev){
        if(G[cur][i] || G[i][cur]) {
            if(circular_vis[i]) return 1;
            circular_vis[i] = 1;
            if(circular(i, cur)) return 1;
        }
    }
    return 0;
}

int gttwo(int s) {
	for (int i = 0; i < n; i++) {
		if (s&(1<<i)) continue;
		int num = 0;
		for (int j = 0; j < n; j++) {
			if (s&(1<<j)) continue;
			if (G[i][j]) num++;
		}
		if (num > 2) return 1;
	}
	return 0;
}

int dfs(int cur) {
    for(int i = 0; i < n; i ++) {
        if(G[i][cur] || G[cur][i]) {
            if(!connect_vis[i]) {
                connect_vis[i] = 1;
                dfs(i);
            }
        }
    }
}
int connected_components() {
    memset(connect_vis, 0, sizeof(connect_vis));
    int cnt = 0;
    for(int i = 0; i < n; i ++) {
        if(!connect_vis[i]) {
            dfs(i);
            cnt ++;
        }
    }
    return cnt;
}

int solve() {
    int image[20][20];              //to restore G after each iteration.
    memcpy(image, G, sizeof(G));

    int minopen = 30;
    for(int itr = 0; itr < (1<<n); itr ++) {//itr iterating from all 0s to all 1s.
        int opencnt = 0;
        for(int j = 0; j < n; j ++) {
            if((itr & (1<<j))) {       //open position j.
                for(int k = 0; k < n; k ++)  G[k][j] = G[j][k] = 0;      //breaking all connections for j.
                opencnt ++;
            }
        }
        int ok = 1;
        for(int j = 0; j < n; j ++) {       //detect for circular pathway.
            memset(circular_vis, 0, sizeof(circular_vis));
            if(circular(j, j)) {
                ok = 0;
                break;
            }
        }
        if(ok && !gttwo(itr)) {     //a vertice with degree > 2 is a the crossing poing of several sequences.
            int connected_components_num = connected_components();
            if((opencnt == 0 && connected_components_num == 1) || (opencnt > 0 && connected_components_num - opencnt <= opencnt + 1)) {
                if(minopen > opencnt) minopen = opencnt;
            }
        }
        memcpy(G, image, sizeof(G));
    }
    printf("Set %d: Minimum links to open is %d\n", ++kase, minopen);
}


int main() {
//    #define DEBUG 1
//    #ifdef DEBUG
//    char fileIn[30] = UVa, fileOut[30] = UVa;
//    strncpy(&fileIn[strlen(fileIn) - 4], ".in\0", 5); strncpy(&fileOut[strlen(fileOut) - 4], ".out\0", 5);
//    freopen(fileIn,"r",stdin);
////    freopen(fileOut,"w",stdout);
//    #endif

    while(scanf("%d", &n) && n) {
        int a, b;
        memset(G, 0, sizeof(G));
        memset(circular_vis, 0, sizeof(circular_vis));
        memset(connect_vis, 0, sizeof(connect_vis));
        while(scanf("%d%d", &a, &b) && a != -1 && b != -1) {
            G[a-1][b-1] = G[b-1][a-1] = 1;
        }
        solve();
    }
    return 0;
}