图论板子

基础

建图

struct edge{
    int u,v;
};
vector<edge> e;
vector<bool> vis;
//较为低效，若用时基本上是需要存边的消息以多次建图，
//或者需要像kruskal那样对边权等进行直接操作。

邻接表，同平常写法。
链式前向星：
int total=-1,head[]...;//需要全部初始化为-1。
void add(int u,int v){
    nxt[++cnt]=head[u];
    head[u]=cnt;
    to[cnt]=v;
}
//遍历时
for(int i=head[u];~i;i=nxt[i]){
    v=to[i];
}

拓扑排序

Kahn算法：不断维护一个入度为0的集合（BFS）

//struct node{ int now, val;};//第一种写法，采用结构体加以判断
vector<int> graph[30];
int intonow[30];
//set<int> total;//现有节点
vector<int> output;
bool toposort(int n){
    queue<int> q;
    output.clear();
    for (int i = 0; i < n;++i)
        if(!intonow[i])
            q.push(i);
    while(!q.empty()){//
        int now = q.front();
        q.pop();
        output.push_back(now);
        for (int i = 0; i < graph[now].size();++i){
            int nxt = graph[now][i];
            if(--intonow[nxt]==0){
                q.push(nxt);
            }
        }
    }
    if(output.size()==n){
        cout<<....;
        return true;
    } else {
        return false;
    }
    /*在这里保留的原因是因为这里的完全建立关系和拓扑排序还是有所不同，在这里就当拓展思路了。
    if(maxs==n){
        cout << "Sorted sequence determined after " << len << " relations: ";//len为函数参数，自己看看要不要罢
        for (int i = 0; i < output.size();++i)
            cout << char('A' + output[i]);
        cout << ".";return true;
    } 
    if(cnt!=total.size()){
        cout << "Inconsistency found after " << len << " relations.";
        return true;
    }
    return false;*/
}

DFS：需要注意的就是最后的output是dfs序，需要reverse

vector<int> graph[N],output;
int marked[N];
bool dfs(int now){
    marked[now]=-1;
    for(int nxt:graph[now]){
        if(marked[nxt]<0) return false;
        if(!marked[nxt]&&!dfs(nxt)) return false;
    }
    marked[now]=1;
    output.push_back(now);
    return true;
}
bool toposort(){
    output.clear(),memset(marked,0,sizeof(marked));
    for(int i=0;i<n;++i)   if(!marked[i]&&!dfs(i)) return false;
    reverse(output.begin(),output.end());
    return true;
}

树链剖分

下面是重链剖分，按照子树大小进行划分。其他如长链剖分，可以直接改改就行。

int fa[N],dep[N],siz[N],hson[N];//父节点，深度，子树大小，重节点
vector<int> a[N];
int top[N],dfn[N],rnk[N],tot;//链顶，dfs序，rnk：逆函数，rnk[dfn[x]]=x;
int dfs1(int u){//记录所需信息
    hson[u]=-1;
    siz[u]=1;
    for(int i=0;i<a[u].size();++i){
        int v=a[u][i];
        if(!dep[v]){
            dep[v]=dep[u]+1;
            siz[u]+=dfs(v,d+1);
            fa[v]=u;
            if(hson[u]==-1||siz[hson[u]]<siz[v]){
                hson[u]=v;
            }
        }
    }
    return siz[u];
}
void dfs2(int u,int nowtop){
    top[u]=nowtop;
    dfn[u]=++tot;
    rnk[cnt]=u;
    if(hson[u]==-1)return;
    dfs2(hson[u],nowtop);
    for(int i=0;i<a[u].size();++i){
        int v=a[u][i];
        if(v!=hson[u]&&v!=fa[u]){
            dfs2(v,v);
        }
    }
}

树

树直径

int fail[N],d[N];
vector<int> a[N];
int road[N],cnt=0;
void dfs(int u,int fa,int &last){
    fail[u]=fa;
    for(int v:a[u]){
        if(v!=fa){
            d[v]=d[u]+1;
            if(d[v]>d[last])  last=v;
            dfs(v,u,last);
        }
    }
}
//使用：
cnt=0;
int begin=0,end=0;
d[1]=0,dfs(1,0,begin);
d[begin]=0;dfs(begin,0,end);

for(int i=end;i;i=fail[i]){
    road[cnt++]=i;
}