void WanQuanDuoBu() {
int T;
cin >> T;
for (int t = 0; t < T; t++) {
int N, M;
cin >> N >> M;
vector<int> aa(N + 1, 0);
vector<vector<int>> arr(N + 1, aa);
for (int i = 0; i < M; i++) {
int x, y;
cin >> x >> y;
arr[x][y] = 1;
arr[y][x] = 1;
}
// 分为多个集合
// 对于新来的点，跟每个集合进行判断
// 跟该集合的每个点都相连，则跟下一个比较，若比较完了，则给该点新建一个集合
// 跟该集合的每个点都不相连，则加入该集合；继续跟下一个集合比较，有不相连则No
vector<set<int> > mySet;
for (int i = 1; i <= N; i++) {
int insetFlag = false;
for (auto &iset : mySet) {
int num = 0;
for (auto item : iset) {
if (arr[i][item] == 1) num++;
}
// 跟每个都相连
if (num == iset.size()) continue;
else if (num == 0) {
// 都不相连，加入集合;若已加入集合，则不符合条件
if (!insetFlag) {
iset.insert(i);
insetFlag = true;
}else{
goto partN;
}
} else {
// 有相连也有不相连，不符合条件，输出NO
goto partN;
}
}
// 比较完了还没加入到集合中，则新建一个
if (!insetFlag) {
set<int> temp;
temp.insert(i);
mySet.push_back(temp);
}
}
cout << "Yes" << endl;
continue;
partN:
cout << "No" << endl;
}
}
#include <iostream>
#include <set>
#include <string>
using namespace std;
int main()
{
int T = 0;
int tmp = 0;
cin >> T;
int tmp2 = T;
string *result = new string[T];
while (T--)
{
bool flg = false;//标记 true找到 false没有找到
int N, M;
set<int> *s;
set<int> *sBian;
cin >> N >> M;
s = new set<int>[N+1];
sBian = new set<int>[N+1];
for (int i = 1; i <= N; i++)
{
for (int j = 1; j <= N; j++)
{
s[i].insert(j);
}
}
for (int i = 0; i < M; i++)
{
int a, b;
cin >> a >> b;
s[a].erase(b);
s[b].erase(a);
sBian[a].insert(b);
sBian[b].insert(a);
}
//遍历所有集合查找任意两个集合里是否都有边
for (int i = 1; i <= N; i++)
{
for (set<int>::iterator it = s[i].begin(); it != s[i].end(); it++)
{
for (int j = 1; j <= N; j++)
{
if (i == j) continue;
for (set<int>::iterator it1 = s[j].begin(); it1 != s[j].end(); it1++)
{
//查找存储的sBian边
if (s[i].find(*it1) == s[i].end())
{
if (sBian[*it].find(*it1) == sBian[*it].end())
{
flg = true;//任意两个集合里没有找到边，输出NO，设置标记量
goto RESULT;
}
}
}
}
}
}
RESULT:
if (flg)
result[tmp++] = "No";
else
result[tmp++] = "Yes";
}
for (int i = 0; i < tmp2; i++)
{
cout << result[i] << endl;
}
return 0;
}AC 55％，说时间超时，求怎么改进
/*
AC 100%
*/
import java.util.*;
public class Main {
public static class Node{
public int value;
public ArrayList<Node> nexts;
public boolean pass;
public Node(int value){
this.value = value;
nexts = new ArrayList<>();
pass = false;
}
}
public static void process(Scanner in){
int n = in.nextInt();
int m = in.nextInt();
HashMap<Integer, Node> map = new HashMap<>();
for(int i = 0; i < n; i++){
map.put(i+1, new Node(i+1));
}
for(int i = 0; i < m; i++){
int f = in.nextInt();
int s = in.nextInt();
Node nf = map.get(f);
Node ns = map.get(s);
nf.nexts.add(ns);
ns.nexts.add(nf);
}
Node n1 = map.get(1);
map.remove(1);
List<Node> xl = n1.nexts;
List<Node> nxl = new ArrayList<>();
for (Map.Entry<Integer, Node> entry : map.entrySet()) {
if(!xl.contains(entry.getValue())){
nxl.add(entry.getValue());
}
}
boolean pan = false;
for(Node node : nxl){
for(Node node1: xl){
if(!node.nexts.contains(node1)){
pan = true;
break;
}
}
}
if(pan){
System.out.println("No");
}else{
System.out.println("Yes");
}
}
public static void main(String[] args){
Scanner in = new Scanner(System.in);
int n = in.nextInt();
for(int i = 0; i < n; i++){
process(in);
}
}
}
t = int(raw_input()) for i in range(t): n, m = map(int, raw_input().split()) data = [ [0]*(n+1) for _ in range(n+1) ] for i in range(m): x, y = map(int, raw_input().split()) data[x][y] = 1 data[y][x] = 1 lset = [] lset.append(set([])) for i in range(1, n+1): flag = False for j in range(len(lset)): num = 0 for h in range(len(lset[j])): if data[i][lset[j][h]] == 1: num += 1 if num == 0: if !flag: ##一 lset[j].add(i) flag = True else: print 'No' if num == len(lset[j]): continue else: print 'No' if !flag: lset.append(set([i])) print 'Yes'
list [ set1, set2, set3]
假设此时满足条件
## 一 ：新添加一个节点，依次比对，节点a，在与set1中的所有点都没有关联，则添加进set1;此时继续比对，set2,若此时节点a仍然与set2中的点都没有关联，但是此时a已经添加进set1,则它将不满足【不同集和的两个点两两有连接！】；若之前并没有添加a进任何集和，那么添加到这个集和。
## 二 ：若此时a与此时集和中的所有元素都有连接，那么继续判断下一个集和。
## 三： 若此时a与集和中的元素既有联系的也有不连接的，那么，直接返回 NO
## 四： 若判断完所有的集和，但是a仍未插入，则建立新的集和。（和之前的集和的元素都有连接的情况）
isaimawang
@ 赛码网
533869549