割点代码

还是有些细节要注意的。。
 1 #include <cstdio>
 2 using namespace std;
 3 
 4 const int maxn=2e5+5;
 5 
 6 inline int min(int a, int b) { return a<b?a:b; }
 7 
 8 class Graph{
 9 public:
10     struct Edge{
11         int to, next; Graph *belong;
12         Edge& operator ++(){ *this=belong->edge[next]; return *this; }
13         int operator *(){ return to; }
14     };
15     void addedge(int u, int v){
16         Edge &e=edge[++cntedge];
17         e.to=v, e.next=fir[u];
18         e.belong=this, fir[u]=cntedge;
19     }
20     Edge gete(int x) { return edge[fir[x]]; }
21 private:
22     int cntedge, fir[maxn];
23     Edge edge[maxn];
24 };
25 
26 int n, m, time, cntgd;
27 int dfn[maxn], low[maxn], gd[maxn];
28 Graph g;
29 
30 //无向图求割点，要么点未访问，要么已退栈，不可能在栈中。
31 void tarjan(int now, int par){
32     dfn[now]=low[now]=++time;
33     int nowson, child=0;
34     for (Graph::Edge e=g.gete(now); *e; ++e){
35         nowson=*e;
36         if (nowson==par) continue;
37         if (!dfn[nowson]){
38             //注意child是递归树中的孩子。。
39             ++child;
40             tarjan(nowson, now);
41             low[now]=min(low[now], low[nowson]);
42             //注意只要有一个分支这样就是割点！
43             if (low[nowson]>=dfn[now]) gd[now]=1;
44         } else low[now]=min(low[now], dfn[nowson]);
45     }
46     //根节点肯定为1呀，应该赋值成0！
47     if (!par&&child==1) gd[now]=0;
48     if (gd[now]) ++cntgd;
49 }
50 
51 int main(){
52     scanf("%d%d", &n, &m);
53     int x, y;
54     for (int i=0; i<m; ++i){
55         scanf("%d%d", &x, &y);
56         g.addedge(x, y); g.addedge(y, x);
57     }
58     for (int i=1; i<=n; ++i)
59         if (!dfn[i]) tarjan(i, 0);
60     printf("%d
", cntgd);
61     for (int i=1; i<=n; ++i)
62         if (gd[i]) printf("%d ", i);
63     return 0;
64 }