树的重心

思路

用一次DFS统计出每个节点下的最大子树的大小，以及子树的总大小，计算出父亲所在子树的大小，取最大值为代价，在扫描一遍，得出答案

#include <bits/stdc++.h>
using namespace std;

int head[500005],Next[1000005],ed[1000005],sum[500005],maxt[500005],n,cnt,ans=1e9,ansid;

void add(int x,int y){
    cnt++;
    Next[cnt]=head[x];
    head[x]=cnt;
    ed[cnt]=y;
}

void dfs(int rt,int f){
    sum[rt]=1;
    for (int i=head[rt];i!=0;i=Next[i]){
        if (ed[i]==f) continue;
        dfs(ed[i],rt);
        sum[rt]+=sum[ed[i]];
        maxt[rt]=max(maxt[rt],sum[ed[i]]);
    }
}

int main(){
    cin>>n;
    int a,b;
    for (int i=1;i<=n-1;++i){
        scanf("%d %d",&a,&b);
        add(a,b);
        add(b,a);
    }
    dfs(1,0);
    for (int i=1;i<=n;++i){
        int tmp=max(n-sum[i],maxt[i]);
        if (tmp<ans){
            ans=tmp;
            ansid=i;
        }
    }
    cout<<ansid<<' '<<ans;
    return 0;
}

拓扑排序

过程：首先将所有出度为0的点加入一个队列
执行while循环，每次取出队头的一个点，找出所有通向它的点，并使这些点出度-1，如果出度变为0，则加入队尾，直到队列为空
例：可达性统计

#include <bits/stdc++.h>
using namespace std;
#define MAXN 30005

bitset <MAXN> ans[MAXN];

int head[MAXN],Next[MAXN],ed[MAXN],sum[MAXN],maxt[MAXN],out[MAXN],n,m,cnt;

void add(int x,int y){
    cnt++;
    Next[cnt]=head[x];
    head[x]=cnt;
    ed[cnt]=y;
}

void topsort(){
    queue <int> q;
    for (int i=1;i<=n;++i){
        if (out[i]==0) q.push(i);
    }
    while (!q.empty()){
        int tmp=q.front();q.pop();
        for (int i=head[tmp];i!=0;i=Next[i]){
            int y=ed[i];
            out[y]--;
            ans[y]=ans[y]|ans[tmp];
            if (out[y]==0) q.push(y);
        }
    }
}

int main(){
    cin>>n>>m;
    int a,b;
    for (int i=1;i<=m;++i){
        scanf("%d %d",&a,&b);
        out[a]++;
        add(b,a);
    }
    for (int i=1;i<=n;++i) ans[i][i]=1;
    topsort();
    for (int i=1;i<=n;++i) printf("%d\n",ans[i].count());
    return 0;
}

树的直径

执行两次DFS，第一次任选一点，找到一条最长路径，第二次以第一次的终点为起点，找一条最长路径即为答案
goto

#include <bits/stdc++.h>
using namespace std;
#define MAXN 100005
int head[MAXN],Next[MAXN*2],ed[MAXN*2],v[MAXN*2],maxt[MAXN],tv[MAXN],n,cnt,ans=-1;

void add(int x,int y,int vi){
    cnt++;
    Next[cnt]=head[x];
    head[x]=cnt;
    ed[cnt]=y;
    v[cnt]=vi;
}

void dfs(int rt,int f){
    maxt[rt]=0;
    int ct=0;
    for (int i=head[rt];i!=0;i=Next[i]){
        if (ed[i]==f) continue;
        dfs(ed[i],rt);
    }
    for (int i=head[rt];i!=0;i=Next[i]){
        if (ed[i]==f) continue;
        maxt[rt]=max(maxt[rt],maxt[ed[i]]+v[i]);
        tv[++ct]=maxt[ed[i]]+v[i];
    }
    int id=0,mt1=0,mt2=0;
    for (int i=1;i<=ct;++i) if (tv[i]>mt1) id=i,mt1=tv[i];
    for (int i=1;i<=ct;++i) if (tv[i]>mt2 && i!=id) mt2=tv[i];
    ans=max(ans,mt1+mt2);
}

int main(){
    cin>>n;
    int a,b,va;
    for (int i=1;i<=n-1;++i){
        scanf("%d %d %d",&a,&b,&va);
        add(a,b,va);
        add(b,a,va);
    }
    dfs(1,0);
    cout<<ans<<endl;
    return 0;
}

本作品采用知识共享署名-非商业性使用-相同方式共享 3.0 未本地化版本许可协议进行许可。
本文链接：https://hs-blog.axell.top/archives/87/