3091133_ac_406ms_4748k.java

北大大牛代码 1240道题的原代码 超级权威

import java.util.*;

public class Main
{
    static boolean [][] map = new boolean [100][100];
    static boolean [] visited = new boolean [100];
    static int cnt, n;
    
    public static void main(String[] args)
    {
        Scanner cin = new Scanner(System.in);
        int i, j, m, t;
        int a, b;
        
        t = cin.nextInt();
        while(t-- > 0)
        {
            n = cin.nextInt();
            m = cin.nextInt();
            for(i = 0; i <= n; i++)
            {
                for(j = 0; j <= n; j++)
                {
                    map[i][j] = false;
                }
            }
            for(i = 1; i <= m; i++)
            {
                a = cin.nextInt();
                b = cin.nextInt();
                map[a][b] = true;
            }
            warshall();
            int ans = 0;
            for(i = 1; i <= n; i++)
            {
                int cnt1 = 0;
                for(j = 1; j <= n; j++)
                {
                    if(map[i][j])
                        cnt1++;
                }
                int cnt2 = 0;
                for(j = 1; j <= n; j++)
                {
                    if(map[j][i])
                        cnt2++;
                }
                if(cnt1 > n/2 || cnt2 > n/2)
                    ans++;
            }
            System.out.println(ans);
        }
    }

    private static void warshall()
    {
        int i, j, m;

        for(i = 1; i <= n; i++)
        {
            for(j = 1; j <= n; j++)
            {
                if(map[j][i])
                {
                    for(m = 1; m <= n; m++)
                    {
                        if(map[i][m])
                        {
                            map[j][m] = true;
                        }
                    }
                }
            }
        }
    }


}