E. Number of Simple Paths
解题思路:这题主要考察了两个知识点。在一个n个点n条边的树中路径有n*(n-1)个。在n个点n-1条边的树中路径有n*(n-1)/2个。这题先求出总共的路径ans,将环看作是一个点a,用ans-以a为顶点的子树中的路径。
#include<bits/stdc++.h> using namespace std; typedef long long ll; typedef long double lf; typedef pair<int,int>P; const int inf = 0x7f7f7f7f; const int N = 2e5+10; const ll mod = 20000311; const double PI = 3.14; int read(){ char ch=getchar();int x=0,f=1; while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while('0'<=ch&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int random(int n){return(ll)rand()*rand()%n;} vector<int>G[N]; int vis[N],d[N]; ll cnt = 0; void dfs(int u){ for(int i = 0;i < G[u].size();i++){ int v = G[u][i]; if(vis[v]) continue; vis[v] = 1; cnt++; dfs(v); } } void solve(){ int n = read(); for(int i = 1;i <= n;i++){ G[i].clear();vis[i] = 1;d[i] = 0; } for(int i = 1;i <= n;i++){ int u = read(),v = read(); G[u].push_back(v); G[v].push_back(u); d[u]++;d[v]++; } queue<int>que; for(int i = 1;i <= n;i++){ if(d[i] == 1) que.push(i); } while(que.size()){ int u = que.front();que.pop(); if(vis[u] == 0) continue; vis[u] = 0; for(int i = 0;i < G[u].size();i++){ int v = G[u][i]; if(d[v] >= 2 && vis[v] == 1){ d[v]--; if(d[v] == 1) que.push(v); } } } ll ans = (ll)n*(n-1); for(int i = 1;i <= n;i++){ if(vis[i]){ cnt = 1; dfs(i); ans -= cnt*(cnt-1)/2; } } cout<<ans<<endl; } int main(){ srand((unsigned)time(0)); //freopen("out.txt","w",stdout); //freopen("in.txt","r",stdin); int t = read(); while(t--){ solve(); } return 0; }
c/c++开发分享E. Number of Simple Paths地址:https://blog.csdn.net/weixin_42868863/article/details/110205447
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/c-cdevelopment/596717.html