CCF通信网络(Java)

规则：正向边与逆向边不能交替走，如4->2->1是对的，但是2->1->3是不对的。
因此不能用无向图
对于每一个点，将它走正向边能到的点 和 走逆向边能到的点 记录下来
若有一个点是： 走正向逆向都到不了的， 那么这个点不可达

这道题写了三个版本

• Floyd版本超时60分，，
• 邻接矩阵深搜60分，超时
• 邻接表满分，因为是稀疏图

邻接表

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
public class 通信网络 {
    static int N = 1001, M = 10010,n,idx1,idx2;
    static int h1[] = new int[N];
    static int e1[] = new int[M];
    static int ne1[] = new int[M];
    static int h2[] = new int[N];
    static int e2[] = new int[M];
    static int ne2[] = new int[M];
    static boolean st[] = new boolean[N];
    static boolean ts[] = new boolean[N];
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        String[] s = br.readLine().split(" ");
        n = Integer.parseInt(s[0]);
        int m = Integer.parseInt(s[1]);
        Arrays.fill(h1, -1);
        Arrays.fill(h2, -1);
        while (m-- > 0) {
            s = br.readLine().split(" ");
            int x = Integer.parseInt(s[0]);
            int y = Integer.parseInt(s[1]);
            add1(x,y);
            add2(y,x);
        }
        int res = 0;
        for(int i= 1;i <= n ; i++) {
            boolean flag = true;
            Arrays.fill(st, false);
            Arrays.fill(ts, false);
            dfs(i,h1,e1,ne1,st);
            dfs(i,h2,e2,ne2,ts);
            for(int k = 1; k <= n ; k ++) {
                if(!st[k]&&!ts[k]) {
                    flag = false;
                    break;
                }
            }
            if(flag) res++;
        }
        bw.write(res+"");
        bw.flush();
    }
    private static void dfs(int u, int[] h, int[] e, int[] ne, boolean[] st) {
        st[u] = true;
        for(int i = h[u];i!=-1;i=ne[i]) {
            int j = e[i];
            if(!st[j]) dfs(j, h, e, ne, st);
        }
    }
    private static void add2(int a, int b) {
        e2[idx2] = b;ne2[idx2] = h2[a];h2[a] = idx2++;
    }
    private static void add1(int a, int b) {
        e1[idx1] = b;ne1[idx1] = h1[a];h1[a] = idx1++;
    }
}

邻接矩阵

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
public class Main {
    static int N = 1001, n;
    static int ab[][] = new int[N][N];
    static int ba[][] = new int[N][N];
    static boolean st[] = new boolean[N];
    static boolean ts[] = new boolean[N];
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        String[] s = br.readLine().split(" ");
        n = Integer.parseInt(s[0]);
        int m = Integer.parseInt(s[1]);
        while (m-- > 0) {
            s = br.readLine().split(" ");
            int x = Integer.parseInt(s[0]);
            int y = Integer.parseInt(s[1]);
            ab[x][y] = 1;
            ba[y][x] = 1;
        }
        int res = 0;
        for(int i= 1;i <= n ; i++) {
            boolean flag = true;
            Arrays.fill(st, false);
            Arrays.fill(ts, false);
            dfs(i,st,ab);
            dfs(i,ts,ba);
            for(int k = 1; k <= n ; k ++) {
                if(!st[k]&&!ts[k]) {
                    flag = false;
                    break;
                }
            }
            if(flag) res++;
        }
        bw.write(res+"");
        bw.flush();
    }
    private static void dfs(int u, boolean[] st, int[][] a) {//优先使用局部变量
        st[u] = true;
        for(int i = 1; i <= n ; i ++) {
            if(a[u][i]!=0&&!st[i]) {
                dfs(i,st,a);
            }
        }
    }

}

Floyd版

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;

public class 通信网络 {
    static int N = 1001, n;
    static int a[][] = new int[N][N];
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        String[] s = br.readLine().split(" ");
        n = Integer.parseInt(s[0]);
        for (int i = 1; i <= n; i++)
            Arrays.fill(a[i], 0x3f3f3f3f);
        int m = Integer.parseInt(s[1]);
        while (m-- > 0) {
            s = br.readLine().split(" ");
            int x = Integer.parseInt(s[0]);
            int y = Integer.parseInt(s[1]);
            a[x][y] = 1;
        }
        floyd();
        int count = 0;
        for (int i = 1; i <= n; i++) {
            boolean flag = true;
            for (int j = 1; j <= n; j++) {
                if (i == j)continue;
                if (a[i][j] == 0x3f3f3f3f && a[j][i] == 0x3f3f3f3f) {
                    flag = false;//存在不联通点Break
                    break;
                }
            }
            if (flag)count++;
        }
        System.out.println(count);
    }

    private static void floyd() {
        for (int k = 1; k <= n; k++) {
            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= n; j++) {
                    if (i == j)continue;
                    a[i][j] = Math.min(a[i][j], a[i][k] + a[k][j]);
                }
            }
        }
    }
}