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;
}
数据检验：
数据输入：
21
17 4 8
1 11
7 5
13 1
3 1
14 5
15 20
9 12
6 8
16 14
18 8
8 4
20 18 10
2 3
12 5
5 9 20
19 20 9 11 2
11 3
4 15
10 3
21 3
0
0
数据输出：
6
p.s.其实图算法还是蛮有趣的~早上看了Kruskal和Prim算法，其实之前已经学过了，现在看也是差不多的感觉，而且还没真正打过代码= =惭愧……
好好学习！天天向上！