输入分为三部分,第一个部分是一个 int,代表这个大班里小朋友的总数。第二部分是一个 int,代表园长采集到的小朋友们的请求数。第三部分是小朋友们的请求,每个请求由两个 int 组成,第一个 int 代表提请求的小朋友,第二个 int 代表他不希望同班的另一位小朋友。
如果所有小朋友的请求都可以被满足,输出 1,否则输出 0。
5 5 1 2 1 3 1 4 1 5 2 3
0
总共有 5 位小朋友,总共采集到了 5 个请求。分别是:1 不希望和 2 同班。1 不希望和 3 同班。1 不希望和 4 同班。1 不希望和 5 同班。2 不希望和 3 同班。不能满足所有人的请求,输出 0。
5 4 1 2 1 3 1 4 1 5
1
总共有 5 位小朋友,总共采集到了 4 个请求。分别是:1 不希望和 2 同班。1 不希望和 3 同班。1 不希望和 4 同班。1 不希望和 5 同班。可以满足所有人的请求,分班方式:1 一个人一班,2、3、4、5 另一班。输出 1。
package com.hhdd.offer.xiaohongshu; import java.util.HashSet; import java.util.Scanner; public class KindeGarten { public static int isSuccess(boolean[][] help){ //set用来代表班级 HashSet<Integer> set1 = new HashSet<>(); HashSet<Integer> set2 = new HashSet<>(); //遍历help二维数组,可以顺序的取出排斥信息 for(int i = 1;i<help.length;i++){ for(int j = 1;j<help.length;j++){ if(help[i][j]){ //如果两个班级都没有i同学,则加入1班;j放入2班 if(!set1.contains(i)&&!set2.contains(i)){ set1.add(i); set2.add(j); }else if(set1.contains(i)){//如果1班含有了i同学,判断1班是否含有j同学 if(set1.contains(j)){ return 0; }else { set2.add(j); } }else if(set2.contains(i)){//如果2班含有了i同学,判断2班是否含有j同学 if(set2.contains(j)){ return 0; }else { set1.add(j); } }else { return 0; } } } } return 1; } public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int peopleNum = scanner.nextInt(); int loopNum = scanner.nextInt(); //set用来代表班级 HashSet<Integer> set1 = new HashSet<>(); HashSet<Integer> set2 = new HashSet<>(); //help二维数组用来存放i同学排斥j同学的信息 boolean[][] help = new boolean[peopleNum + 1][peopleNum + 1]; for (int i = 0; i < loopNum; i++) { int row = scanner.nextInt(); int col = scanner.nextInt(); help[row][col] = true; } int ans = isSuccess(help); System.out.println(ans); } }
#include<iostream> #include<stdio.h> #include<algorithm> using namespace std; int n,m,book[500100],flag; vector<int>arr[500100]; void dfs(int f,int x,int category) { int ne = (category == 1)?2:1; book[x] = category; for(int i=0;i<arr[x].size();i++) { if(arr[x][i]!=f) { if(book[arr[x][i]]==0) { dfs(x,arr[x][i],ne); } else if(book[arr[x][i]]!=ne) { flag = 1; break; } } } } int main() { cin>>n; cin>>m; for(int i=1;i<=m;i++) { int a,b; cin>>a>>b; arr[a].push_back(b); arr[b].push_back(a); } for(int i=1;i<=n;i++) { if(!book[i]) dfs(0,i,1); } if(flag) cout<<0<<endl; else cout<<1<<endl; return 0; }二分染色问题 直接dfs 搞什么花里胡哨
#include <iostream> #include <map> #define INIT() ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); using namespace std; int main() { int n = 0; int k = 0; INIT(); cin >> n >> k; map<int, bool> cls1, cls2; for(int i = 0; i < k; i++) { int stu1, stu2; cin >> stu1 >> stu2; if((cls1[stu1] && cls1[stu2]) ||(cls2[stu1] && cls2[stu2])) { cout << 0 << endl; return 0; } if(cls1[stu1] && !cls2[stu2]) cls2[stu2] = true; else if(cls2[stu1] && !cls1[stu2]) cls1[stu2] = true; else { cls1[stu1] = true; cls2[stu2] = true; } } cout << 1 << endl; return 0; }
#include<cstdio> (802)#include<cstring> using namespace std; int main() { int first[10000]={0},second[10000]={0},n,m;//两个班被讨厌的人赋值为一; scanf("%d%d",&m,&n); for(int i=0;i<n;i++) { int a,b; scanf("%d %d",&a,&b); if(first[a]==0&&second[b]==0)//a,b所在的班级没人讨厌他们 { first[b]=1;//a进1班,b被讨厌,不能进 second[a]=1; } else if(first[b]==0&&second[a]==0) { first[a]=1;//a进2班 second[b]=1; } else { printf("0\n"); return 0; } } printf("1\n"); return 0; }
#include <bits/stdc++.h> using namespace std; int main(){ int n,m,x,y; cin>>n>>m; bool a[n+1],b[n+1]; memset(a,false,sizeof(a)); memset(b,false,sizeof(b)); for(int i=0;i<m;i++){ cin>>x>>y; if(!a[x] && !b[y] && !a[y] && !b[x]){ a[x] = b[y] = true; }else if(b[x] && !a[y]) a[y] = true; else if(a[x] && !b[y]) b[y] = true; } bool flag = true; for(int i=1;i<=n;i++) if(a[i]==b[i] && a[i]) flag = false; cout<<(flag?1:0)<<endl; return 0; }
""" 深度优先搜索+条件判断 """ import sys def dfs(group, a, step): if step == len(a): return True ret = False if group[a[step][0]] == 0 and group[a[step][1]] == 0: group[a[step][0]] = 1 group[a[step][1]] = -1 ret = dfs(group, a, step + 1) group[a[step][0]] = -1 group[a[step][1]] = 1 ret = ret or dfs(group, a, step + 1) elif group[a[step][0]] == 0: group[a[step][0]] = -group[a[step][1]] ret = dfs(group, a, step + 1) elif group[a[step][1]] == 0: group[a[step][1]] = -group[a[step][0]] ret = dfs(group, a, step + 1) elif group[a[step][0]] * group[a[step][1]] == -1: ret = dfs(group, a, step + 1) else: ret = False return ret if __name__ == '__main__': # sys.stdin = open("input.txt", "r") n = int(input()) m = int(input()) a = [] for _ in range(m): a.append(list(map(int, input().strip().split()))) group = [0] * (n + 1) ans = dfs(group, a, 0) print(1 if ans else 0)
#八皇后算法思想
n = int(input())#小朋友个数
m = int(input())#要求数目
mat = [[0]*(n) for i in range(n)]
for i in range(m):
res = [int(j) for j in input().split()]
mat[res[0]-1][res[1]-1]=1
mat[res[1]-1][res[0]-1]=1
#定义判断第index个同学所处第color个班级是否去前index个同学相矛盾
def check(state,index,color):
for i in range(index):
if state[i]==color and mat[i][index]==1:
return False
return True
def fenban(state,index):
if index==n:
return 1
for color in (0,1):
if check(state,index,color):
state[index]= color
if fenban(state,index+1)==1:
return 1
return 0
state=[0]*n#学生分配的班级
print(fenban(state,0))
n = int(input()) q = int(input()) a = [] b = [] for i in range(q): ai,bi = list(map(int,input().split())) a.append(ai) b.append(bi) x = [] y = [] for i in range(q): if (a[i] in x and b[i] in x) or (a[i] in y and b[i] in y): print(0) exit() elif a[i] not in x and a[i] not in y and b[i] not in x and b[i] not in y: x.append(a[i]) y.append(b[i]) elif a[i] in x and b[i] not in x: x.append(a[i]) y.append(b[i]) elif b[i] in x and a[i] not in x: x.append(b[i]) y.append(a[i]) elif a[i] in y and b[i] not in y: y.append(a[i]) x.append(b[i]) elif b[i] in y and a[i] not in y: y.append(b[i]) x.append(a[i]) print(1)
#include <bits/stdc++.h> using namespace std; int main(){ set<int> arr1,arr2; int n,k,flag=1; cin>>n>>k; for(int i=0;i<k;i++){ int a,b; cin>>a>>b; if(arr1.find(a)==arr1.end()&&arr2.find(a)==arr2.end()){ arr1.insert(a); arr2.insert(b); } else if(arr1.find(a)!=arr1.end()){ if(arr1.find(b)==arr1.end()) arr2.insert(b); else{ flag=0; break; } } else if(arr2.find(a)!=arr2.end()){ if(arr2.find(b)==arr2.end()) arr1.insert(b); else{ flag=0; break; } } } cout<<flag; return 0; }
def main(): n = int(input()) request_n = int(input()) x = [] y = [] for i in range(request_n): req = input().split() req = [int(r) for r in req] if req[0] not in x and req[0] not in y: x.append(req[0]) y.append(req[1]) continue if req[0] in x and req[1] in x: print(0) return elif req[0] in y and req[1] in y: print(0) return elif req[0] in x and req[1] not in y: y.append(req[1]) elif req[0] in y and req[1] not in x: x.append(req[1]) print(1) return if __name__ == "__main__": main()
import java.util.HashSet; import java.util.Scanner; public class Main{ public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int stdNum = scanner.nextInt(); scanner.nextLine(); int requNum = scanner.nextInt(); scanner.nextLine(); HashSet<Object> left = new HashSet<>(); HashSet<Object> right = new HashSet<>(); boolean isOk = true; for (int i=0;i<requNum;i++){ int l = scanner.nextInt(); int r = scanner.nextInt(); if (left.contains(l) && !right.contains(r) && !left.contains(r)){ right.add(r); scanner.nextLine(); continue; } if (right.contains(l) && !right.contains(r) && !left.contains(r)){ left.add(r); scanner.nextLine(); continue; } if (left.contains(l) && left.contains(r) || right.contains(l) && right.contains(r)){ System.out.println(0); isOk=false; break; } left.add(l); right.add(r); scanner.nextLine(); } if(isOk){ System.out.println(1); } } }
using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; namespace TestMachine { public static class T01_FenBan { public class Request { public int num; public int notlike; } public static void Main() { string input = Console.ReadLine(); int max = int.Parse(input); input = Console.ReadLine(); int RequsetCount = int.Parse(input); List<int> Clase1 = new List<int>(); List<int> Clase2 = new List<int>(); List<Request> AllRequest = new List<Request>(); for (int i = 0; i < RequsetCount; i++) { input = Console.ReadLine(); string[] inputs = input.Split(' '); int num = int.Parse(inputs[0]); int notlike = int.Parse(inputs[1]); AllRequest.Add(new Request() { num = num, notlike = notlike }); } int answer = DealRequest(AllRequest,Clase1,Clase2,0)?1:0; Console.WriteLine(answer); } private static bool DealRequest(List<Request> allrequest, List<int> class1, List<int> class2, int i) { bool answer = true; if (i == allrequest.Count) { return true; } Request _request = allrequest[i]; if (class1.Count == 0 || class2.Count == 0) { class1.Add(_request.num); class2.Add(_request.notlike); answer = DealRequest(allrequest, class1, class2, ++i); } else if ((class1.Exists(t => t == _request.num) && class1.Exists(t => t == _request.notlike)) || (class2.Exists(t => t == _request.num) && class2.Exists(t => t == _request.notlike))) { return false; } else if ((class1.Exists(t => t == _request.num) && class2.Exists(t => t == _request.notlike))||(class2.Exists(t => t == _request.num) && class1.Exists(t => t == _request.notlike))) { answer = DealRequest(allrequest, class1, class2, ++i); } else if (class1.Exists(t => t == _request.num) && !class2.Exists(t => t == _request.notlike)) { class2.Add(_request.notlike); answer = DealRequest(allrequest, class1, class2, ++i); } else if (class2.Exists(t => t == _request.num) && !class1.Exists(t => t == _request.notlike)) { class1.Add(_request.notlike); answer = DealRequest(allrequest, class1, class2, ++i); } else if (!class2.Exists(t => t == _request.num) && !class1.Exists(t => t == _request.notlike)) { List<int> temp1 = CopyList(class1); List<int> temp2 = CopyList(class2); temp1.Add(_request.num); temp2.Add(_request.notlike); bool tempanswer = DealRequest(allrequest, temp1, temp2, ++i); if (!tempanswer) { temp1 = CopyList(class1); temp2 = CopyList(class2); temp2.Add(_request.num); temp1.Add(_request.notlike); tempanswer = DealRequest(allrequest, temp1, temp2, ++i); } else return true; if (!tempanswer) return false; } else if (class2.Exists(t => t == _request.num) && class1.Exists(t => t == _request.notlike)) { answer = false; } return answer; } public static List<int> CopyList(List<int> a) { List<int> b = new List<int>(); foreach (int item in a) { b.Add(item); } return b; } } }
import java.util.*; public class Main{ public static void main(String[] args){ Scanner sc=new Scanner(System.in); int childrenNum=sc.nextInt(); int queryNum=sc.nextInt(); HashSet<Integer> class1=new HashSet<>(); HashSet<Integer> class2=new HashSet<>(); for(int i=0;i<queryNum;++i){ int child1=sc.nextInt(); int child2=sc.nextInt(); boolean flag11=class1.contains(child1); boolean flag12=class1.contains(child2); boolean flag21=class2.contains(child1); boolean flag22=class2.contains(child2); if((flag11 && flag12)||(flag21 && flag22)){ System.out.println(0); return; }else if(flag11 && !flag22){ class2.add(child2); }else if(flag12 && !flag21){ class2.add(child1); }else if(flag21 && !flag12){ class1.add(child2); }else if(flag22 && !flag11){ class1.add(child1); }else if(!flag11 && !flag12 && !flag21 && !flag22){ class1.add(child1); class2.add(child2); } } System.out.println(1); } }
#include<iostream> using namespace std; int main() { int a,b,c,d,e; bool This=1; cin>>a; int *p=new int[a*a]; int *q=new int[a*a]; int *r=new int[a*a]; cin>>b; for(int i=0;i<a;i++) { for(int j=0;j<a;j++) { p[(i)*a+(j)]=0; r[(i)*a+(j)]=0; if(i==j) { q[(i)*a+(j)]=1; }else { q[(i)*a+(j)]=0; } } } for(int i=0;i<b;i++) { cin>>c>>d; p[(c-1)*a+(d-1)]=1; p[(d-1)*a+(c-1)]=1; } e=a; if(e%2==0) { e=e-1; } for(int m=0;m<e;m++) { for(int i=0;i<a;i++) { for(int j=0;j<a;j++) { for(int k=0;k<a;k++) { r[(i)*a+(j)]+=q[(j)*a+(k)]*p[(k)*a+(i)]; } } } for(int i=0;i<a;i++) { for(int j=0;j<a;j++) { q[(i)*a+(j)]= r[(i)*a+(j)]; r[(i)*a+(j)]=0; } } } for(int i=0;i<a;i++) { if(q[(i)*a+i]!=0) { This=0; } } cout<<This; delete [] r; delete [] q; delete [] p; return 0; }
public class Test { private static int []color; private static int [][]G; public static void main(String[]args){ Scanner sc = new Scanner(System.in); int n = sc.nextInt()+1; //节点数目 int k = sc.nextInt(); //边数 G = new int[n][n]; //邻接矩阵 color = new int[n]; //节点颜色,默认没有颜色0,其他两种颜色-1,1 for(int i = 0; i< k; i++){ int x = sc.nextInt(); int y = sc.nextInt(); G[x][y] = 1; G[y][x] = 1; } //如果是连通图,则一次dfs即可访问所有位置 //但题目没有说明,故要依次检查各个顶点的情况 for(int i = 1; i< n; i++){ if(color[i] == 0){ if(!dfs(i,1)){ System.out.println("0"); return; } } } System.out.println("1"); } private static boolean dfs(int v, int c){ color[v] = c; for(int j = 1; j< G[v].length; j++){ //是相邻节点 if(G[v][j] == 1){ //相邻点没有染色 if(color[j] == 0){ //给相邻点染色,若相邻点的子结点中存在相邻点同色的情况,则返回false if(dfs(j,-c) == false){ return false; } } //相邻点同色 if(color[j]==c){ return false; } } } return true; } }
n=int(input()) k=int(input()) a=[] for i in range(k): a.append(list(map(int,input().split()))) a.sort() a1=[a[0][0]] a2=[a[0][1]] res=[] #把不能随便分班的先分班,暂时可以随便分的计入到res中 for i in a[1:]: if i[0] in a1 and i[1]not in a2: a2.append(i[1]) elif i[0] in a2 and i[1]not in a1: a1.append(i[1]) elif i[1] in a1 and i[0]not in a2: a2.append(i[0]) elif i[1] in a2 and i[0]not in a1: a1.append(i[0]) elif i[0]not in a1 and i[0]not in a2 and i[1]not in a1 and i[1]not in a2 : res.append(i) temp=[] #对res中的学生进行分班,知道res中只剩下可以随机分班不影响互斥关系的 while res!=temp: temp=res[:] for i in res: if i[0] in a1 and i[1]not in a2: a2.append(i[1]) res.remove(i) elif i[0] in a2 and i[1]not in a1: a1.append(i[1]) res.remove(i) elif i[1] in a1 and i[0]not in a2: a2.append(i[0]) res.remove(i) elif i[1] in a2 and i[0]not in a1: a1.append(i[0]) res.remove(i) n=a1+a2 n.sort() m=list(set(n)) m.sort() if n!=m: print(0) else: print(1)