略高难度的dfs

题目链接：https://ac.nowcoder.com/acm/contest/6874/F

import java.math.*;
import java.util.*;

  //=学习dfs中，现在是弄了半天弄不出来

public class Main {
    static int ans,a[][];
    static boolean v[];
    public static void main(String[] args) {


        Scanner scan = new Scanner(System.in);
        int n=scan.nextInt(),m=scan.nextInt();
        a=new int[n+1][n+1];
        for(int i=1;i<=m;i++) {
            int x=scan.nextInt(),y=scan.nextInt();
            a[y][x]=1;
        }
        for(int i=1;i<=n;i++) {
            v=new boolean[n+1];
            ans=0;
            dfs(i,n);
            System.out.println(ans);
        }
    }
    public static void dfs(int x,int n) {
        for(int i=1;i<=n;i++) {
            if(!v[i]&&a[x][i]==1) {
                ans++;
                v[i]=true;
                dfs(i,n);        //继续深搜

            }
        }
    }
}

首先定义一个n+1行n+1列的二维数组，然后呢，把输入的a，b放到一个元素中，赋值为1.接下来先写一个for，这个for循环6次，从1开始。首先在每次定义的时候，创建一个v[]的布尔数组，用来记录对应位置上是否有元素。ans作为计数器，接下来就开始dfs。dfs中，x为for循环中的i，也就是从第一行开始的遍历，可以知道，如果v[i]为false（这里没有元素），然后a[x][i]也就是遍历a[1][1~7]，都没有元素，所以ans为0，同理第二行也是一样，因为没有元素，所以ans=0，第三行遍历时，因为1>3，所以呢a[3][1] == 1，然后v[1]=true,然后呢继续以dfs（1,6）搜索，但是第一行的时候结果为0，所以呢ans=1。第四行也是一样。第五航的时候dfs（5,6），a[5][3]==1之后继续搜索dfs（3,6）,搜索到之后ans=2，那么继续外循环，此时到了a[5][4]，因为4>5，所以ans++，然后继续搜索dfs（4,6），ans++，所以最后ans=4.