图论(1)

图的存储

直接存边

int e[N];
e[1]=3;//1->3有条边

邻接表

int h[N],e[N],ne[N],idx;
void add(int a,int b){
    e[idx]=b,ne[idx]=h[a],h[a]=idx,idx++;
}
void init(){
    meset(h,-1,size of(h));//所有头结点为空
}

也可以用vector e[N];

图的遍历

树和图的深度优先搜索

void dfs(int u){
    st[u]=true;
    
    for(int i=h[u];i!=-1;i=ne[i])//遍历出边
    {
        int j=e[i];
        if(!st[j]) dfs(j);
    }
}

846 树的重心
有n个结点，n-1条边
求删除重心剩余各连通块中数的最大值
重心：删除树中一个结点，剩余的各个连通块的数的最大值最小，这个点就是重心
输入描述

1. 结点数n（$1\le n\le 10^5$）;
2. n-1行 a b表示一条边

输出格式
输出一个整数m,表示结果
样例
输入样例

9
1 2
1 7
1 4
2 8
2 5
4 3
3 9
4 6

输出样例

4

算法思路
删去每个结点，然后存储最大连通图，然后在储存的连通图里选一个最小的。
深度优先遍历可以求得子树的大小

# 1
## 2
- 8
- 5
## 4
- 3
    - 9
- 6
## 7

算法代码

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

using namespace std;
const int N=100010,M=N*2;
int n,m;
int h[N],e[M],ne[M],idx;
bool st[N];//go
int ans=N;//init max

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

//以u为根的树中的结点数量，返回的并不是我们要的而是过程中要的
int dfs(int u){
    st[u]=true;
    
    int sum=1,res=0;//sum存储子树数量，res存储每次删点的连通块最大值
    
    for(int i=h[u];i!=-1;i=ne[i])//读入u边指向的边，只要不为空就继续读
    {
       int j=e[i]; 
       if(!st[j]){
           int s=dfs(j);
           res=max(res,s);
           sum+=s;
       }
    }
    res=max(res,n-sum);
    ans=min(ans,res);
    return sum;
}
int main(){
    cin>>n;
    memset(h,-1,sizeof(h));
    
    for(int i=0;i<n-1;i++){
        int a,b;
        cin>>a>>b;
        add(a,b),add(b,a);
    }
    
    dfs(1);
    cout<<ans<<endl;
    return 0;
}

BFS

while(queue不空){
    t<-队头；
    拓展t所有相邻的点x
    if(x未遍历){
        queue<-x;
        d[x]=d[t]+1;
    }
}

846图中点的层次 题目描述
n个点，m条边，可能有重边和自环
边长度都是1，点的编号1-n；
请你求出1到n号点的最短距离，如果不能到输出-1；
输入格式

1. n,m（$1\le n,m\le 10^5$）
2. m行a，b边
   输出格式
   输出1到n的最短距离
   输入样例

4 5
1 2
2 3
3 4
1 3
1 4

输出样例

1

code

#include <iostream>
#include <cstring>
using namespace std;
const int N=100010;
int n,m;
int d[N],q[N];
int h[N],e[N],ne[N],idx;
void add(int a,int b){
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
int bfs(){
    int hh=0,tt=0;
    q[0]=1;//1号点入队
    
    memset(d,-1,sizeof(d));//init d
    
    d[1]=0;
    while(hh<=tt){
        int t=q[hh++];//队列指针出队
        
        for(int i=h[t];i!=-1;i=ne[i]){//i指向j的指针
            int j=e[i];//点
            if(d[j]==-1){
                d[j]=d[t]+1;//t是上一个点
                q[++tt]=j;
            }
        }
    }
    if(d[n] == -1) return -1;
    return d[n];
}
int main(){
    cin>>n>>m;
    memset(h,-1,sizeof(h));
    for(int i=0;i<m;i++){
        int a,b;
        cin>>a>>b;
        add(a,b);
    }
    cout<<bfs()<<endl;
    return 0;
}

有向图的拓扑序列

拓扑队列：所有的边都是从前指向后；
必须是有向无环图才可能有拓扑序（DAG）;
有向无环图也叫拓扑图

queue <-所有入度为0的点
while(queue不空){
    t<-队头；
    枚举t所有出边t到j；
    删掉t->j;//d[j]--入度;
    if(d[j]==0)    queue<-j;
}

一个有向无环图一定至少存在一个入度为零的点
有向图的拓扑序列
n点m边，点的编号1-n可能有重边和自环
对于图中的每条边 (x,y) ，x 在 A中都出现在 y 之前，则称 A 是该图的一个拓扑序列。
请输出拓扑序列，不存在输出-1；
输入格式

1. n点m边；（$1\le n,m\le 10^5$）
2. m行x，y边

输出格式
存在拓扑排序，输出合法的拓扑排序；
不存在输出-1；
输入样例

3 3
1 2
2 3
1 3

输出样例

1 2 3

code

#include <iostream>
#include <cstring>

using namespace std;
const int N=100010;
int n,m;
int h[N],e[N],ne[N],idx;
int q[N],d[N];
void add(int a,int b){
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
bool topsort(){
    int hh=0,tt=-1;
    
    for(int i=1;i<=n;i++){
        if(d[i]==0)
            q[++tt]=i;
    }
    
    while(hh<=tt){
        int t=q[hh++];
        
        for(int i=h[t];i!=-1;i=ne[i]){
            int j=e[i];
            if(--d[j]==0)
                q[++tt]=j;
        }
    }
    return tt==n-1;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cin>>n>>m;
    memset(h,-1,sizeof(h));
    
    for(int i=0;i<m;i++){
        int a,b;
        cin>>a>>b;
        add(a,b);
        d[b]++;
    }
    if(topsort()==false) cout<<-1<<" ";
    else for(int i=0;i<n;i++) cout<<q[i]<<" ";
    return 0;
}