分享完全多部图-非常简单的思路
刚才第一次发帖，我忘记题目了，现在修改了一下。。。哈哈哈
题目:同一个集合里面不能连通，不同集合里面必须连通
基本思路:如果1和3. 4. 5不连通，那么3 4 5之间一定不能连通！否则，不是完全多部图
我们只需对每个节点进行上述判断就可以了
题目:同一个集合里面不能连通，不同集合里面必须连通
基本思路:如果1和3. 4. 5不连通，那么3 4 5之间一定不能连通！否则，不是完全多部图
我们只需对每个节点进行上述判断就可以了
public class Main {
public static void main(String[] args) {
Scanner scanner=new Scanner(System.in);
int t = scanner.nextInt();
for(int i=0;i<t;i ) {
int n = scanner.nextInt();
int m = scanner.nextInt();
int[][] graph = new int[n 1][n 1];
for(int j=0;j<m;j ) {
int A = scanner.nextInt();
int B = scanner.nextInt();
graph[A][B] = 1;
graph[B][A] = 1;
}
int k = 0;
for( k=1;k<=n;k ) {
List<Integer> temp = new ArrayList<>();
for(int h=1;h<=n;h ) {
if(k==h) continue;
if(graph[k][h]!=1) temp.add(h);
}
if(isValid(graph,temp)==false) {
System.out.println("No");
break;
}
}
if(k>n) System.out.println("Yes");
}
}
private static boolean isValid(int[][] graph,List<Integer> list) {
for(int i=0;i<list.size();i ) {
for(int j=i 1;j<list.size();j ) {
if(graph[list.get(i)][list.get(j)]==1) return false;
}
}
return true;
}
}
#京东##Java工程师#
查看10道真题和解析
投递美团等公司10个岗位 >