树图的存储

邻接矩阵

就二维数组 不用说

邻接表

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<vector>
#include<queue>
#include<stack>
#include<cstring>
#include<unordered_map>
using namespace std;
typedef long long LL;
const int N=10000,M=2*N;
int h[N],e[M],ne[M],idx;
void add(int a,int b){
    e[idx]=b;   
    ne[idx]=h[a];//next指针
    h[a]=idx++;
}
int main(){
    memset(h,-1,sizeof h);
  return 0;
}
//  freopen("testdata.in", "r", stdin);

846. 树的重心

https://www.acwing.com/problem/content/848/

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100010, M = N * 2;

int n;
int h[N], e[M], ne[M], idx;
int ans = N;
bool st[N];

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

int dfs(int u)
{
    st[u] = true;

    int size = 0, sum = 0;
    for (int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        if (st[j]) continue;

        int s = dfs(j);
        size = max(size, s);
        sum += s;
    }

    size = max(size, n - sum - 1);
    ans = min(ans, size);

    return sum + 1;
}

int main()
{
    scanf("%d", &n);

    memset(h, -1, sizeof h);

    for (int i = 0; i < n - 1; i ++ )
    {
        int a, b;
        scanf("%d%d", &a, &b);
        add(a, b), add(b, a);
    }

    dfs(1);

    printf("%d\n", ans);

    return 0;
}

847. 图中点的层次

https://www.acwing.com/problem/content/849/

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<vector>
#include<queue>
#include<stack>
#include<cstring>
#include<unordered_map>
using namespace std;
typedef long long LL;
const int N=100010,M=100010;
int h[N],e[M],ne[M],idx;
int d[N];
int n,m;
int ans=-1;
void add(int a,int b){
    e[idx]=b;
    ne[idx]=h[a];
    h[a]=idx++;
}
queue<int>q;
int main(){
    memset(h,-1,sizeof h);
    memset(d,-1,sizeof d);
    cin>>n>>m;
    for(int i=0;i<m;i++){
        int a,b;
        cin>>a>>b;
        add(a,b);
    }
    d[1]=0;
    q.push(1);
    while(q.size()){
        int t=q.front();
        q.pop();
        for(int i=h[t];i!=-1;i=ne[i]){
            int j=e[i];
            if(d[j]==-1){
                d[j]=d[t]+1;
                q.push(j);
            }
        }
    }
    cout<<d[n]<<endl;
  return 0;
}
//  freopen("testdata.in", "r", stdin);

有向图的拓扑序列

https://www.acwing.com/problem/content/850/

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<vector>
#include<queue>
#include<stack>
#include<cstring>
#include<unordered_map>
using namespace std;
typedef long long LL;
const int N=1e5+5;
int h[N],ne[N],e[N],idx;
int ru[N];
bool st[N];
int n,m;
vector<int >ans;
void add(int a,int b){
    e[idx]=b;
    ne[idx]=h[a];
    h[a]=idx++;
}
void Delete(int u){
    for(int i=h[u];i!=-1;i=ne[i]){
        int j=e[i];
        ru[j]--;
    }
    st[u]=true;
    return ;
}
int main(){
    memset(h,-1,sizeof h);
    cin>>n>>m;
    for(int i=0;i<m;i++){
        int a,b;
        cin>>a>>b;
        add(a,b);
        ru[b]++;
    }
    while(1){
        int flag=0;
        for(int i=1;i<=n;i++){
            if(ru[i]==0 && !st[i]){
                flag=1;
                Delete(i);
                ans.push_back(i);
            }
        }
        if(!flag){
            break;
        }
    }
    if(ans.size()<n) puts("-1");
    else {
        for(int i=0;i<ans.size();i++){
            cout<<ans[i]<<" ";
        }
    }
  return 0;
}
//  freopen("testdata.in", "r", stdin);

AcWing 图论打卡