洛谷 P3388 【模板】割点（割顶）

P3388 【模板】割点（割顶）

题目背景

割点

题目描述

给出一个

输入格式

第一行输入

下面

输出格式

第一行输出割点个数

第二行按照节点编号从小到大输出节点，用空格隔开

输入输出样例

输入 #1

输出 #1

1 
5

说明/提示

对于全部数据，

点的编号均大于

tarjan图不一定联通。

代码

 1 #include <bits/stdc++.h>
 2 #define ll long long
 3 #define ull unsigned long long
 4 #define ms(a,b) memset(a,b,sizeof(a))
 5 const int inf=0x3f3f3f3f;
 6 const ll INF=0x3f3f3f3f3f3f3f3f;
 7 const int maxn=1e6+10;
 8 const int mod=1e9+7;
 9 const int maxm=1e3+10;
10 using namespace std;
11 vector<int>ve[maxn];
12 // dfn[u]表示顶点u第几个被访问（首次）
13 int dfn[maxn];
14 // low[u]表示顶点u及其子树中的点，通过非父子边（回边），能够回溯到的最早的点（dfn最小）的dfn值（但不能通过连接u与其父节点的边）
15 // 对于边(u,v)，如果low[v]>=dfn[u]，则u是割点
16 int low[maxn];
17 int vis[maxn];
18 int id;
19 // if(u是v的子边)
20 //     low[u]=min(low[u],low[v])
21 // else
22 //     low[u]=min(low[u],dfn[v])
23 void tarjan(int u,int father)
24 {
25     int child=0;
26     dfn[u]=low[u]=++id;
27     int sz=ve[u].size();
28     for(int i=0;i<sz;i++)
29     {
30         int v=ve[u][i];
31         // 如果v未被访问过
32         if(!dfn[v])
33         {
34             tarjan(v,father);
35             low[u]=min(low[u],low[v]);
36             // u是割点 
37             if(low[v]>=dfn[u]&&u!=father)
38                 vis[u]=1;
39             if(u==father)
40                 child++;
41         }
42         // 如果v被访问过，且u不是v的父亲
43         low[u]=min(low[u],dfn[v]);
44     }
45     // u是根节点并且子树超过两个
46     if(child>=2&&u==father)
47         vis[u]=1;
48 }
49 int main(int argc, char const *argv[])
50 {
51     #ifndef ONLINE_JUDGE
52         freopen("in.txt", "r", stdin);
53         freopen("out.txt", "w", stdout);
54         srand((unsigned int)time(NULL));
55     #endif
56     ios::sync_with_stdio(false);
57     cin.tie(0);
58     int n,m;
59     cin>>n>>m;
60     int x,y;
61     while(m--)
62     {
63         cin>>x>>y;
64         ve[x].push_back(y);
65         ve[y].push_back(x);
66     }
67     for(int i=1;i<=n;i++)
68         if(!dfn[i])
69             tarjan(i,i);
70     int ans=0;
71     for(int i=1;i<=n;i++)
72         if(vis[i])
73             ans++;
74     cout<<ans<<endl;
75     for(int i=1;i<=n;i++)
76         if(vis[i])
77             cout<<i<<" ";
78     cout<<endl;
79     #ifndef ONLINE_JUDGE
80         cerr<<"Time elapsed: "<<1.0*clock()/CLOCKS_PER_SEC<<" s."<<endl;
81     #endif
82     return 0;
83 }