ABC378

F - Add One Edge 2

题意：一颗有n个顶点的树，第i条边双向连接顶点ui和vi，在给定的树上添加一条不定向边，总能得到一个正好有一个循环的图。在这些图中，有多少个满足所有顶点都有阶数3

分析：每次阶数为3的dfs找阶数为2的个数，两个阶数为2的即可凑出循环图，所以满足条件的个数为cnt*(cnt-1)/2

代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
typedef long long ll;
const int N=2e5+10;
vector<int>G[N];
int n;
int deg[N];
bool vis[N];
int cnt=0;
ll ans=0;
void dfs(int v,int fa=0){//无父节点 fa=0作初始值
    if(deg[v] != 3){//由于作为可连接的点 可能连接了多个联通块不打标记
        cnt += (deg[v]==2);
        return;
    }
    vis[v] = 1;
    for(auto x:G[v]){//x是节点v相连的
        if(x == fa) continue;
        dfs(x,v);
    }
}
void sol(){
   cin>>n;
   for(int i = 1;i < n;++i){
        int u,v;
        cin>>u>>v;
        G[u].push_back(v);
        G[v].push_back(u);
        ++deg[u];++deg[v];
    }
    for(int i=1;i<=n;++i){
        // 找 deg=3 的连通块
        if(deg[i] != 3) continue;
        if(vis[i]) continue;
        cnt = 0;
        dfs(i);
        ans += cnt*(cnt-1)/2;
    }
    cout<<ans<<"\n";    
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    int t;t=1;
    for(int i=1;i<=t;i++)sol();
    return 0;
}
​

原文地址：https://blog.csdn.net/m0_74310050/article/details/143576805

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！