1 条题解
-
0
思路
无向图low值判割点,DFS根需至少两个树子女,非根才用low[child]>=dfn[u];按行解析无度数的邻接名单并去除双向重复描述,多组0分隔,n<100。
参考程序(C++11)
#include <bits/stdc++.h> using namespace std; int main(){ios::sync_with_stdio(false);cin.tie(nullptr);int n;while(cin>>n&&n){string line;getline(cin,line);vector<vector<int>>g(n,vector<int>(n));while(getline(cin,line)){istringstream in(line);int u;if(!(in>>u))continue;if(u==0)break;int v;while(in>>v)g[u-1][v-1]=g[v-1][u-1]=1;}vector<int>dfn(n),low(n),cut(n);int timer=0;function<void(int,int)>dfs=[&](int u,int parent){dfn[u]=low[u]=++timer;int children=0;for(int v=0;v<n;v++)if(g[u][v]){if(!dfn[v]){children++;dfs(v,u);low[u]=min(low[u],low[v]);if(parent!=-1&&low[v]>=dfn[u])cut[u]=1;}else if(v!=parent)low[u]=min(low[u],dfn[v]);}if(parent==-1&&children>1)cut[u]=1;};for(int u=0;u<n;u++)if(!dfn[u])dfs(u,-1);cout<<accumulate(cut.begin(),cut.end(),0)<<'\n';}}
- 1