Problem Address：http://poj.org/problem?id=1144
其实这道题看了一下就知道要求割点了，但是目前还没学会怎么求。
所以上网找了下资料。
资料是找对了，慢慢地也看懂了，但是写代码的时候写错了，结果悲剧地WA了一次，然后就在那里折腾了好久好久。
都觉得那个代码不完全了。
到最后（很后……）发现是自己写错了个单词。
然后就AC了。
庆祝一下学会了求割点。顺便看懂了可以顺便求割边。
于是自己也用了邻接表和邻接矩阵两种方法试了一下。
由于数据规模也比较小，所以邻接矩阵提交后花的时间更少，不像邻接表那样要老是申请和释放空间。
以下贴代码：
由于在不断的调试之中，代码有点潦草= =
邻接表：
#include <iostream>using namespace std;int pre[105], back[105];bool visited[105];int min(int a, int b){ if (a<b) return a; else return b;}struct node{ int ver; node *next;};node computer[105];void dfs(int i, int root, int &index, int &count){ int n=0; bool critical=false; node *t; visited[i] = true; pre[i] = index; back[i] = pre[i]; index++; for (t=computer[i].next; t; t=t->next) { if (!visited[t->ver]) { dfs(t->ver, root, index, count); if (i==root) { n++; if (n==2) critical=true; } else { back[i] = min(back[i],back[t->ver]); if (back[t->ver]>=pre[i]) { critical=true; } } } else { back[i] = min(back[i],pre[t->ver]); } } if (critical) { count++; }}int main(){ node *temp, *t; int n,i,x,y,ct,root,index; while(scanf("%d", &n)!=EOF) { if (n==0) break; for (i=1; i<=n; i++) computer[i].next=NULL; for (i=1; i<=n; i++) visited[i] = false; while(scanf("%d", &x)) { if (x==0) break; while(getchar()!='/n') { scanf("%d", &y); temp = computer[x].next; computer[x].next = (node*)malloc(sizeof(node)); computer[x].next->ver = y; computer[x].next->next = temp; temp = computer[y].next; computer[y].next = (node*)malloc(sizeof(node)); computer[y].next->ver = x; computer[y].next->next = temp; } } index = 1; ct = 0; root = 1; dfs(root, root, index, ct); printf("%d/n", ct); for (i=1; i<=n; i++) { temp = computer[i].next; while(temp) { t = temp->next; free(temp); temp = t; } } } return 0;}
邻接矩阵：
#include <iostream>using namespace std;bool map[105][105];int pre[105], back[105];bool visited[105];int n;int min(int a, int b){ if (a<b) return a; else return b;}void dfs(int i, int root, int &index, int &count){ int num=0,j; bool critical=false; visited[i] = true; pre[i] = index; back[i] = index; index++; for (j=1; j<=n; j++) { if (map[i][j]) { if (!visited[j]) { dfs(j, root, index, count); if (i==root) { num++; if (num==2) critical=true; } else { back[i] = min(back[i],back[j]); if (back[j]>=pre[i]) { critical=true; } } } else { back[i] = min(back[i],pre[j]); } } } if (critical) { count++; }}int main(){ int i,j,x,y,ct,root,index; while(scanf("%d", &n)!=EOF) { if (n==0) break; for (i=1; i<=n; i++) { for (j=1; j<=n; j++) { map[i][j] = false; } } for (i=1; i<=n; i++) visited[i] = false; while(scanf("%d", &x)) { if (x==0) break; while(getchar()!='/n') { scanf("%d", &y); map[x][y] = true; map[y][x] = true; } } index = 1; ct = 0; root = 1; dfs(root, root, index, ct); printf("%d/n", ct); } return 0;}
数据检验：
数据输入：
2117 4 81 117 513 13 114 515 209 126 816 1418 88 420 18 102 312 55 9 2019 20 9 11 211 34 1510 321 300
数据输出：
6
p.s.其实图算法还是蛮有趣的~早上看了Kruskal和Prim算法，其实之前已经学过了，现在看也是差不多的感觉，而且还没真正打过代码= =惭愧……
好好学习！天天向上！
