E. Number of Simple Paths
程序员文章站
2022-06-24 12:25:52
E. Number of Simple Paths解题思路:这题主要考察了两个知识点。在一个n个点n条边的树中路径有n*(n-1)个。在n个点n-1条边的树中路径有n*(n-1)/2个。这题先求出总共的路径ans,将环看作是一个点a,用ans-以a为顶点的子树中的路径。#includeusing namespace std;typedef long long ll;typedef long double lf;typedef pair
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;
}
本文地址:https://blog.csdn.net/weixin_42868863/article/details/110205447