1 条题解

  • 0
    @ 2026-10-25 23:19:37

    思路

    无向图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

    信息

    ID
    1585
    时间
    1000ms
    内存
    10MiB
    难度
    普及
    标签
    递交数
    1
    已通过
    1
    上传者