残剑

Description
雅克布在一次洞穴探险中发现了一柄残剑。剑刃上有一些凹陷的点以及连接着点的凹痕。剑旁边有一个石碑，碑上有一些类似于中世纪的风格的文字：
“亲爱的圆桌骑士，我将这把剑赐予你，请用你们的智慧使它重现往日神威。让剑开封的秘密在于剑刃上的‘星命图’，上面的‘星命点’通过凹痕互相连通，只要你们封住关键的星命点，宝剑就可以在月光下得到重生。所谓的关键的星命点是指如果封住了这个点，那么星命图就不再连通。”
雅克布通过观察得到，星命图由N的星命点组成（编号为1到N），任何两个点之间至多连有一条凹痕。
雅克布现在告诉你星命图，要你帮他找到那些需要封住的点。
Input
第一行一个整数N（N<=100）
下接若干行，每行两个整数a,b表示点a,b之间连通
文件以0 0 结束
Output
一行，按编号从小到大输出你找到的点,每个数字后面一个空格
Sample Input
5
1 2
1 3
2 3
1 4
4 5
0 0
Sample Output
1 4

sol：求割点

对于边u—>v，求割边是判断low[v]>dfn[u]是否成立，而求割点是判断low[v]>=dfn[u]是否成立。

如果是根节点，需要判断是否有两次或以上的这样的边。

代码如下:

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define maxn 10001
 4 #define maxm 50001
 5 int sta[maxm],End[maxm],now[maxm],pre[maxm];
 6 int m,n,cnt,tot,top,total,ans,group;
 7 int low[maxn],dfn[maxn],asd;
 8 bool ok[maxn];
 9 void build(int x,int y)
10 {
11     tot++;
12     sta[tot]=x;
13     End[tot]=y;
14     pre[tot]=now[x];
15     now[x]=tot;
16 }
17 void dfs(int k,int fa)
18 {
19     dfn[k]=++cnt;
20     low[k]=cnt;
21     for(int i=now[k];i;i=pre[i])
22     {
23         if (End[i]==fa) continue;
24         if(!dfn[End[i]])
25         {
26             dfs(End[i],k);
27             low[k]=min(low[k],low[End[i]]);
28             if(dfn[k]==1)
29             {
30                 if(low[End[i]]>=dfn[k])
31                     asd++;
32                 if(asd>1) 
33                    ok[k]=true;
34             }
35             else 
36                 if(low[End[i]]>=dfn[k]) ok[k]=true;      
37         }
38         else 
39              low[k]=min(low[k],dfn[End[i]]);
40     }
41 }
42 int main()
43 {
44     cin>>n;
45     while(1)
46     {
47         int x,y;
48         cin>>x>>y;
49         if(x==0&&y==0) break;
50         m++;
51         build(x,y);
52         build(y,x);
53     }
54     dfs(1,0);
55     for(int i=1;i<=n;i++) if(ok[i]) 
56     {
57             printf("%d ",i);
58     }
59     printf("
");
60 }