欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

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

相关标签: 拓扑排序 思维