AcWing算法基础课 Level-2 第三讲 搜索与图论

#include 
using namespace std;
const int N = 1e5 + 10;

// head 表示头结点的下标
// e[i] 表示节点i的值
// ne[i] 表示节点i的next指针是多少
// idx 存储当前已经用到了哪个点
int head, e[N], ne[N], idx;

// 初始化
void init()
{
    head = -1;
    idx = 0;
}

// 将x插到头结点
void add_to_head(int x)
{
    e[idx] = x, ne[idx] = head, head = idx ++ ;
}

// 将x插到下标是k的点后面
void add(int k, int x)
{
    e[idx] = x, ne[idx] = ne[k], ne[k] = idx ++ ;
}

// 将下标是k的点后面的点删掉
void remove(int k)
{
    ne[k] = ne[ne[k]];
}

int main()
{
    int m;
    cin >> m;

    init(); // 初始化

    while (m -- )
    {
        int k, x;
        char op;
        cin >> op;

        if (op == 'H')
        {
            cin >> x;
            add_to_head(x);
        }
        else if (op == 'D')
        {
            cin >> k;
            if (!k) head = ne[head];
            else remove(k - 1);
        }
        else{
            cin >> k >> x;
            add(k - 1, x);
        }
    }

    for (int i = head; i != -1; i = ne[i]) cout << e[i] << " ";
    cout << endl;
    return 0;
}

#include 
using namespace std;
const int N = 1e5 + 10;

int idx, l[N], r[N], e[N];

//在节点a的右边插入x
void insert(int a, int x)
{
    e[idx] = x;
    l[idx] = a, r[idx] = r[a];
    l[r[a]] = idx, r[a] = idx ++ ;
}

//删除节点a
void remove(int a)
{
    r[l[a]] = r[a];
    l[r[a]] = l[a];
}

int main()
{
    //0是左端点，1是右端点
    l[1] = 0, r[0] = 1, idx = 2;

    int m;
    cin >> m;
    while (m -- )
    {
        string op;
        int k, x;
        cin >> op;

        if (op == "L")
        {
            cin >> x;
            insert(0, x);
        }
        else if (op == "R")
        {
            cin >> x;
            insert(l[1], x);
        }
        else if (op == "D")
        {
            cin >> k;
            remove(k + 1);
        }
        else if (op == "IL")
        {
            cin >> k >> x;
            insert(l[k + 1], x);
        }
        else 
        {
            cin >> k >> x;
            insert(k + 1, x);
        }
    }

    for (int i = r[0]; i != 1; i = r[i]) cout << e[i] << " ";

    return 0;
}

• 树是一种特殊的图，无向图又是特殊的有向图；因此考虑有向图如何存储即可；有向图的存储 ：稠密图->邻接矩阵；邻接表，存储每个点可以到达哪些点
• 图的邻接表存储方式是为每一个结点开个表，存的意思是从这个点可以走到哪些点，这个单链表内部点的顺序是无关紧要的
• n个点所以是n-1条边；cstring头文件；边数这里设置为点数的两倍，在开数组时注意；st数组记录是否遍历过该点，在遍历一个点所有能到达的点的过程中，为了避免走回头路，也要用到st数组；注意当前这颗子树的大小 和 去掉这个点后最大联通块 之间的关系；图用的是多条单链表，所以注意每次都要初始化h数组；无向图，所以add两次；这里随便挑一个点都可以开始dfs，树从哪个点都可以开始当根

#include 
#include 		// memset
#include 

using namespace std;

const int N = 1e5 + 10, M = 2 * N;

int n, m;

// head, e[M],ne[M],idx; 是一条单链表
// h[N], e[M],ne[M],idx; 是N条单链表
int h[N], e[M], ne[M], idx;

bool st[N];  // 用st数组存一下哪些点已经被遍历过了

int ans = N;  //记录一个全局最大值

// 在a对应的单链表中插入一个节点b
void add(int a, int b)
{
    e[idx] = b;         // 表示第idx条边指向b点
    ne[idx] = h[a];  // ne[idx]表示第idx条边的下一条边是 a点的邻接链表的第一条边
    h[a] = idx++;    // head[a]表示将a点的邻接链表的第一条边更新为第idx条边
}

// u表示当前已经dfs到的这个点
// 以u为根的子树中， 点的数量
int dfs(int u)
{
    st[u] = true;  // 标记一下， 当前这个点已经被搜索过

    int sum = 1;  // 记录当前子树大小
    int res = 0;  // 把u这个点删除之后， 每一个联通块的最大值

    for (int i = h[u]; i != -1; i = ne[i]) {
        int j = e[i];  // 当前这个链表中的节点， 对应图中的点的编号是多少
        if (!st[j]) {
            int s = dfs(j);     // j这棵子树的大小
            res = max(res, s);  //最大的联通块大小
            sum += s;
        }
    }
    res = max(res, n - sum);
    ans = min(ans, res);
    return sum;
}

int main()
{
    // 一条单链表 head初始化为-1
    // n条单链表，把所有的head初始化为-1
    memset(h, -1, sizeof h);

    cin >> n;
    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；dist表示距离，-1表示走不到，初始化为-1

#include 
#include 
#include 

using namespace std;

const int N = 1e5 + 10;

int n, m;
int h[N], e[N], ne[N], idx;
int dist[N];

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

int bfs()
{
    memset(dist, -1, sizeof dist);
    queue q;

    q.push(1);
    dist[1] = 0;

    while (q.size())
    {
        auto t = q.front();
        q.pop();

        for (int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];
            if (dist[j] == -1)
            {
                dist[j] = dist[t] + 1;
                q.push(j);
            }
        }
    }

    return dist[n];
}

int main()
{

    memset(h, -1, sizeof h);

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

    printf("%dn", bfs());
}

• 有向无环图也被称为拓扑图
• 拓扑序列 ：所有的边都从前指向后，那么所有入度为0的点都可以作为起点

#include 
#include 
#include 

using namespace std;

const int N = 1e5 + 10;

int h[N], e[N], ne[N], idx;
int top[N];
int d[N];
int cnt = 0;
int n, m;

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

bool topsort()
{
    queue q;
    for (int i = 1; i <= n; i ++ )
        if (!d[i])
            q.push(i);
    
    while (q.size())
    {
        auto t = q.front();
        q.pop();
        top[cnt ++ ] = t;
        
        for (int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];
            d[j] -- ;
            if (!d[j])
                q.push(j);
        }
    }
    
    return cnt == 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);
        d[b] ++ ;
    }
    
    if (!topsort()) puts("-1");
    else
    {
        for (int i = 0; i < n; i ++ )
        {
            cout << top[i];
            if (i != n - 1) cout << ' ';
        }
    }
    
    return 0;
}

#include 
#include 

using namespace std;

const int N = 1e5 + 10;

int h[N], e[N], ne[N], idx;
int q[N];
int d[N];

int n, m;

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])
            q[ ++ tt] = i;
    
    while (hh <= tt)
    {
        auto t = q[hh ++ ];
        
        for (int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];
            d[j] -- ;
            if (!d[j])
                q[ ++ tt] = j;
        }
    }
    
    return tt + 1 == n;
}

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);
        d[b] ++ ;
    }
    
    if (!topsort()) puts("-1");
    else
    {
        for (int i = 0; i < n; i ++ )
        {
            cout << q[i];
            if (i != n - 1) cout << ' ';
        }
    }
    
    return 0;
}

• 稠密图，邻接矩阵；稀疏图，邻接表
• 建图时要把所有边初始化为正无穷，，为了应对重边，每次保留最短的边；先将所有距离初始化为正无穷，起点距离为0，遍历n-1轮，每轮确定一个点，找到未标记的点中距离最小的，然后用这个点更新其它点的距离，再标记这个距离最小的点，表示已经用它更新过
• 基于贪心思想，只适用于所有边的长度都是非负数的图

#include 
#include 

using namespace std;

const int N = 510;

int g[N][N];
int dist[N];
bool st[N];

int n, m;

int dijkstra()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    for (int i = 0; i < n - 1; i ++ )
    {
        int t = -1;
        for (int j = 1; j <= n; j ++ )
            if (!st[j] && (t == -1 || dist[t] > dist[j]))
                t = j;
        
        for (int j = 1; j <= n; j ++ )
            dist[j] = min(dist[j], dist[t] + g[t][j]);
        
        st[t] = true;
    }
    
    if (dist[n] == 0x3f3f3f3f) return -1;
    return dist[n];
}

int main()
{
    memset(g, 0x3f, sizeof g);
    
    cin >> n >> m;
    for (int i = 0; i < m; i ++ )
    {
        int a, b, c;
        cin >> a >> b >> c;
        g[a][b] = min(g[a][b], c);
    }
    
    printf("%d", dijkstra());
    
    return 0;
}

• 稀疏图 -> 邻接表（相比多了w数组记录权值