12389. 割点

n个顶点m条边，请求割点

输入格式:

第一行给定三个整数 n，m 。n 个城镇，m 条道路(双向道路)。接下来给出 m 行，每行两个正整数表示这两个城镇之间有边相连。

输出格式:

一个整数，有几个关键城市。

样例 1 :

输出:
3

说明:
3 6 8是关键城市

https://www.acoj.com/problems/12389

 1 #include <cstdio>
 2 #include <vector>
 3 #include <cstring>
 4 
 5 using namespace std;
 6 
 7 const int max_n = 100000+10;
 8 
 9 int n,m;
10 vector<int> g[max_n];
11 int num[max_n],low[max_n],flag[max_n],time_index,root;
12 
13 void dfs(int cur,int fa)
14 {
15     int child=0;
16 
17     ++time_index;
18     num[cur]=time_index;
19     low[cur]=time_index;
20 
21     for(int i=0;i<g[cur].size();++i)
22     {
23         int v=g[cur][i];
24         if(num[v]==0)
25         {
26             ++child;
27             dfs(v,cur);
28             low[cur]=min(low[v],low[cur]);
29             if(cur!=root && num[cur]<=low[v])
30             {
31                 flag[cur]=1;
32             }
33             if(cur==root && child==2)
34             {
35                 flag[cur]=1;
36             }
37         }
38         else if(v!=fa)
39         {
40             low[cur]=min(num[v],low[cur]);
41         }
42     }
43 
44 }
45 
46 void solve()
47 {
48     time_index=0;
49     root=1;
50     memset(num,0,sizeof(num));
51     memset(flag,0,sizeof(flag));
52 
53     dfs(1,1);
54 
55     int ans=0;
56     for(int i=1;i<=n;++i)
57     {
58         if(flag[i])
59         {
60             //printf("%d ",i);
61             ++ans;
62         }
63     }
64     printf("%d",ans);
65 }
66 
67 int main()
68 {
69     scanf("%d %d",&n,&m);
70     int a,b;
71     for(int i=0;i<m;++i)
72     {
73         scanf("%d %d",&a,&b);
74         g[a].push_back(b);
75         g[b].push_back(a);
76     }
77 
78     solve();
79 
80     return 0;
81 }