ACM模版

描述


题解

很简单的一道题，但是前天上 java 课老师让我们练题，给大家出了一道这题，一看数据就知道这个一定是 dfs+邻接表，然而我没有跟着专业学 java，倒是主攻的 C/C++，所以写 C/C++ 版也就分分钟的事，可是写 java 版的我好心塞，java没有指针，猛一下不知道链表怎么写，我也不会用 java 的类库，java 满共学了十天不到，还是一年前自学的，倒是可以看懂，自己写却问题百出，由于能力有限，课上花了二十几分钟写了一个邻接矩阵+dfs 的解法，只能过部分数据，可是邻接表我就不知道具体语法怎么实现了，折腾了好久才解决，不太理解 java 的有些错误提示，太头疼了，让我给同学写题解，赶鸭子上架……

这里提供三种代码，一种是为了方便大家学习 dfs 的 java 写的邻接矩阵+dfs 的解法（代码One），只能过部分数据，但是对于学习 dfs 已经足够了，一种 C/C++写的邻接表+dfs 的解法（代码 Two），提交 AC 了，还有一种 java 写的邻接表+dfs 的解法（代码 Three），由于官网现在在维护中，所以就不提交了，本地测试没问题。

代码

One:

package javatest;

import java.util.Scanner;

public class NodeTongXin {
   
    static int N, M;
    static int graph[][] = new int[1000][1000]; // 邻接矩阵
    static int vis[][] = new int[1000][1000];   // 标识矩阵，标识(i,j)是否用过
    static long cnt = 0;                        // 累加器
    private static Scanner input;

    static void dfs(int st, int step)           // 起点，剩余边数
    {
        if (step == 0)                          // 剩余0条边后 GG
        {
            cnt++;                              // 找到一条路累加器自增
            return ;                            // 结束这一分支，开始回溯
        }
        for (int i = 1; i <= N; i++)            // 寻找下一个结点
        {
            if (vis[st][i] == 0 && graph[st][i] != 0 && i != st)    // 要求(st,i)未传输过，并且连通
            {                                   // i和st不能相等，否则就不是一条边了
                vis[st][i] = 1;                 // 更改边的使用情况
                vis[i][st] = 1;                 // 无向图，(i,st)也得更新
                dfs(i, step - 1);               // 递归，深入下一层查找，用最新找到的结点为起点深入，剩余边数减一
                vis[st][i] = 0;                 // 回溯过程，需要将深入查找之前更改的使用状态还原
                vis[i][st] = 0;                 // 同上
            }
        }
    }

    public static void main(String[] argv)
    {
        input = new Scanner(System.in);

        N = input.nextInt();
        M = input.nextInt();

        int a, b;
        for (int i = 0; i < M; i++)             // 一共M条边
        {
            a = input.nextInt();
            b = input.nextInt();
            graph[a][b] = 1;                    // (a,b)连通
            graph[b][a] = 1;                    // 无向图，(b,a)也连通
        }

        for (int i = 1; i <= N; i++)            // 枚举所有结点，作为起点开始深度搜索
        {           
            dfs(i, 3);                          // 初始剩余三条边
        }

        System.out.println(cnt);                // 输出累加器结果即为所有结果
    }
}

Two:

#include <iostream>
#include <cstdio>
#include <vector>

using namespace std;

const int MAXN = 10001;

int n, m, cnt = 0;
vector<int> graph[MAXN];

void dfs(int last, int st, int step)
{
    if (step == 0)
    {
        cnt++;
        return ;
    }
    for (int i = 0; i < graph[st].size(); i++)
    {
        if (graph[st][i] != last)
        {
            dfs(st, graph[st][i], step - 1);
        }
    }
}

int main(int argc, const char * argv[])
{
    cin >> n >> m;

    int a, b;
    for (int i = 0; i < m; i++)
    {
        scanf("%d%d", &a, &b);
        graph[a].push_back(b);
        graph[b].push_back(a);
    }

    for (int i = 1; i <= n; i++)
    {
        dfs(-1, i, 3);
    }

    cout << cnt << '\n';

    return 0;
}

Three:

package javatest;

import java.util.Scanner;

public class NodeTongXin2 {
      
    static class Node                           // 邻接表结点，实际上是链表结点
    {
        int v;                                  // 线段端点
        Node nt;                                // 链表的下一个结点

        Node()                                  // 实例化时初始化
        {
            nt = null;
        }

        Node(int v_, Node nt_)                  // 实例化时初始化，重载上一个函数
        {
            v = v_;
            nt = nt_;
        }
    }

    static int N, M;
    static Node graph[] = new Node[10005];      // 申请一个表头，Node 数组代表表头
    static long cnt = 0;                        // 累加器
    private static Scanner input;

    static void dfs(int last, int st, int step) // 上一个点，起点，剩余边数
    {
        if (step == 0)                          // 剩余0条边后 GG
        {
            cnt++;                              // 找到一条路累加器自增
            return ;                            // 结束这一分支，开始回溯
        }
        Node nd = graph[st].nt;                 // 查找表头，找到链表起点
        for (; nd != null; nd = nd.nt)          // 遍历链表
        {
            if (nd.v != last)                   // 不能等于上一个结点
            {
                dfs(st, nd.v, step - 1);
            }
        }
    }

    public static void main(String[] argv)
    {
        input = new Scanner(System.in);

        N = input.nextInt();
        M = input.nextInt();

        for (int i = 0; i <= N; i++)
        {
            graph[i] = new Node();              // 实例化对象
        }

        int a, b;
        Node nd = null;
        for (int i = 0; i < M; i++)             // 一共M条边
        {
            a = input.nextInt();
            b = input.nextInt();
            nd = new Node(b, graph[a].nt);      // 头插法插入链表
            graph[a].nt = nd;                   
            nd = new Node(a, graph[b].nt);
            graph[b].nt = nd;
        }

        for (int i = 1; i <= N; i++)            // 枚举所有结点，作为起点开始深度搜索
        {           
            dfs(-1, i, 3);                      // 初始上一个结点为-1，剩余三条边
        }

        System.out.println(cnt);                // 输出累加器结果即为所有结果
    }
}

注释只能这么详细了，如果还不懂，那我就只能给你们画图模拟 dfs 每一步的执行过程了，但是我真心不想这样，我没有装 PS……