京东java编程第一题，ac代码
//京东笔试第一题，ac代码 //思路为先将图反转，将反转后的图分为几个完全连通部件， //此时用BFS或DFS找出所有的连通部件，判断每个连通部件是否为完全图import java.util.*;
public class Main {
public static boolean[][] matrix =null;
public static boolean[] visited = null;
public static ArrayList<Integer> dgroup=null;
public static void main(String[]args)
{
Scanner sc = new Scanner(System.in);
int T = sc.nextInt();
while(T--!=0) {
int n,m;
int s,t;
n=sc.nextInt(); m=sc.nextInt();
if(m==0) {
System.out.println("Yes");
continue;
}
matrix= new boolean[n][n];
visited = new boolean[n];
for(boolean e: visited) {
e = false;
}
for(int i=0; i<n; i++) {
for(int j=0; j<n; j++) {
matrix[i][j]=false;
}
}
for(int i=0; i<m; i++) {
s=sc.nextInt(); t=sc.nextInt();
matrix[s-1][t-1] = true;
matrix[t-1][s-1] = true;
}
boolean flag = true;
for(int i=0; i<n; i++) {
if(visited[i] == false) {
dgroup = new ArrayList<Integer>();
Divide(n,i);
if(!check(dgroup)) {
flag = false;
}
}
}
if(!flag) {
System.out.println("No");
} else {
System.out.println("Yes");
}
}
}
public static void Divide(int n, int s) {
visited[s] = true;
dgroup.add(s);
for(int i=0; i<n ; i++)
{
if(visited[i] == false && i != s) {
if(!matrix[i][s]) {
Divide(n, i);
}
}
}
}
public static boolean check(ArrayList<Integer> group) {
for(int i=0; i<group.size()-1; i++) {
for(int j=i+1; j<group.size(); j++) {
if(matrix[group.get(i)][group.get(j)]) {
return false;
}
}
}
return true;
}
}
#京东##笔试题目#
投递蔚来等公司10个岗位 >
中移(苏州)软件技术有限公司工作强度 29人发布