内容：染色划分，带权并查集，扩展并查集
Arpa’s overnight party and Mehrdad’s silent entering
题目链接
题目大意
个点围成一圈，分为
对，对内两点不同染色同时，相邻3个点之间必须有两个点不同染色问构造出一种染色方案 解题思路
将每对进行的连边看作一类边将为满足相邻3个点必须有两个点不同染色的边，看作二类边满足构造方案，即将
个点形成一个二分图，无奇环对于只有一类边，形不成环，端点不同对于二类边与一类边组合才能形成环将二类边定义为
成环的情况只能，如下图
由于一类边不可能相连，中间必然是二类边，一类边交换，所以环上的点数为二类边的总点数，一定为偶数，只能形成偶环，构造成立利用带权并查集实现 import java.io.*;import java.math.BigInteger;import java.util.Arrays;import java.util.BitSet;import java.util.HashMap;import java.util.HashSet;import java.util.Iterator;import java.util.LinkedList;import java.util.PriorityQueue;import java.util.Queue;import java.util.StringTokenizer;import java.util.Vector;public class Main{static int find(int x,int[] fa,int[] relation) {if(x==fa[x])return x;else {int f=fa[x];fa[x]=find(fa[x], fa, relation);relation[x]=(relation[x]+relation[f])%2;return fa[x];}}public static void main(String[] args) throws IOException{AReader input=new AReader(); PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out)); int n=input.nextInt(); int[] fa=new int[2*n+1]; int[] relation=new int[2*n+1]; for(int i=1;i<=2*n;++i)fa[i]=i; int[] a=new int[n+1]; int[] b=new int[n+1]; for(int i=1;i<=n;++i) { int x=input.nextInt(); int y=input.nextInt(); a[i]=x;b[i]=y; int fx=find(x, fa, relation); int fy=find(y, fa, relation); if(fx==fy)continue; fa[fx]=fy; relation[fx]=(relation[y]+1-relation[x]+2)%2; } for(int i=1;i<=n;++i) {//一圈 int x=2*i; int y=i==n?1:2*i+1; int fx=find(x, fa, relation); int fy=find(y, fa, relation); if(fx==fy)continue; fa[fx]=fy; relation[fx]=(relation[y]+1-relation[x]+2)%2; } for(int i=1;i<=n;++i) { find(a[i], fa, relation); find(b[i], fa, relation); int x=relation[a[i]]+1; int y=relation[b[i]]+1; out.println(x+" "+y); } out.flush(); out.close();}staticclass AReader{ BufferedReader bf; StringTokenizer st; BufferedWriter bw; public AReader(){ bf=new BufferedReader(new InputStreamReader(System.in)); st=new StringTokenizer(""); bw=new BufferedWriter(new OutputStreamWriter(System.out)); } public String nextLine() throws IOException{ return bf.readLine(); } public String next() throws IOException{ while(!st.hasMoreTokens()){ st=new StringTokenizer(bf.readLine()); } return st.nextToken(); } public char nextChar() throws IOException{ //确定下一个token只有一个字符的时候再用 return next().charAt(0); } public int nextInt() throws IOException{ return Integer.parseInt(next()); } public long nextLong() throws IOException{ return Long.parseLong(next()); } public double nextDouble() throws IOException{ return Double.parseDouble(next()); } public float nextFloat() throws IOException{ return Float.parseFloat(next()); } public byte nextByte() throws IOException{ return Byte.parseByte(next()); } public short nextShort() throws IOException{ return Short.parseShort(next()); } public BigInteger nextBigInteger() throws IOException{ return new BigInteger(next()); } public void println() throws IOException { bw.newLine(); } public void println(int[] arr) throws IOException{ for (int value : arr) { bw.write(value + " "); } println(); } public void println(int l, int r, int[] arr) throws IOException{ for (int i = l; i <= r; i ++) { bw.write(arr[i] + " "); } println(); } public void println(int a) throws IOException{ bw.write(String.valueOf(a)); bw.newLine(); } public void print(int a) throws IOException{ bw.write(String.valueOf(a)); } public void println(String a) throws IOException{ bw.write(a); bw.newLine(); } public void print(String a) throws IOException{ bw.write(a); } public void println(long a) throws IOException{ bw.write(String.valueOf(a)); bw.newLine(); } public void print(long a) throws IOException{ bw.write(String.valueOf(a)); } public void println(double a) throws IOException{ bw.write(String.valueOf(a)); bw.newLine(); } public void print(double a) throws IOException{ bw.write(String.valueOf(a)); } public void print(char a) throws IOException{ bw.write(String.valueOf(a)); } public void println(char a) throws IOException{ bw.write(String.valueOf(a)); bw.newLine(); }}}食物链
题目链接
题目大意
个点，
对关系每个点可能为
类，它们之间满足
吃
，
吃
，
吃
对关系中，
表示
同类，
表示
吃
依次处理
对关系，若当前关系与之前的关系矛盾，则视为错误
（自己吃自己），均视为错误问有多少对错误 解题思路
对
个点进行
种颜色的染色划分类似黑白染色利用带权并查集或扩展并查集实现详见图论笔记 扩展并查集
import java.io.*;import java.math.BigInteger;import java.util.Arrays;import java.util.BitSet;import java.util.HashMap;import java.util.HashSet;import java.util.Iterator;import java.util.LinkedList;import java.util.PriorityQueue;import java.util.Queue;import java.util.StringTokenizer;import java.util.Vector; public class Main{static int find(int x,int[] fa) {if(x==fa[x])return x;else return fa[x]=find(fa[x], fa);}public static void main(String[] args) throws IOException{AReader input=new AReader(); PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out)); int n=input.nextInt(); int k=input.nextInt(); int[] fa=new int[3*n+1]; for(int i=1;i<=3*n;++i)fa[i]=i; int ans=0; for(int i=1;i<=k;++i) { int op=input.nextInt(); int x=input.nextInt(); int y=input.nextInt(); if(x>n||y>n) { ans++; continue; } if(op==1) { if(find(x, fa)==find(y+n, fa)||find(y, fa)==find(x+n, fa)) { //x吃y或y吃x //x吃y=>xA->yB,xB->yC,xC->yA //y吃x=>yA->xB,yB->xC->yC->xA ans++; continue; } fa[find(x, fa)]=find(y, fa); fa[find(x+n, fa)]=find(y+n, fa); fa[find(x+2*n, fa)]=find(y+2*n, fa); }else { if(x==y) { ans++; continue; } if(find(x, fa)==find(y, fa)||find(y, fa)==find(x+n, fa)) { //x和y是同类,y吃x ans++; continue; } fa[find(x, fa)]=find(y+n, fa); fa[find(x+n, fa)]=find(y+2*n, fa); fa[find(x+2*n, fa)]=find(y, fa); } } out.print(ans); out.flush(); out.close();}staticclass AReader{ BufferedReader bf; StringTokenizer st; BufferedWriter bw; public AReader(){ bf=new BufferedReader(new InputStreamReader(System.in)); st=new StringTokenizer(""); bw=new BufferedWriter(new OutputStreamWriter(System.out)); } public String nextLine() throws IOException{ return bf.readLine(); } public String next() throws IOException{ while(!st.hasMoreTokens()){ st=new StringTokenizer(bf.readLine()); } return st.nextToken(); } public char nextChar() throws IOException{ //确定下一个token只有一个字符的时候再用 return next().charAt(0); } public int nextInt() throws IOException{ return Integer.parseInt(next()); } public long nextLong() throws IOException{ return Long.parseLong(next()); } public double nextDouble() throws IOException{ return Double.parseDouble(next()); } public float nextFloat() throws IOException{ return Float.parseFloat(next()); } public byte nextByte() throws IOException{ return Byte.parseByte(next()); } public short nextShort() throws IOException{ return Short.parseShort(next()); } public BigInteger nextBigInteger() throws IOException{ return new BigInteger(next()); } public void println() throws IOException { bw.newLine(); } public void println(int[] arr) throws IOException{ for (int value : arr) { bw.write(value + " "); } println(); } public void println(int l, int r, int[] arr) throws IOException{ for (int i = l; i <= r; i ++) { bw.write(arr[i] + " "); } println(); } public void println(int a) throws IOException{ bw.write(String.valueOf(a)); bw.newLine(); } public void print(int a) throws IOException{ bw.write(String.valueOf(a)); } public void println(String a) throws IOException{ bw.write(a); bw.newLine(); } public void print(String a) throws IOException{ bw.write(a); } public void println(long a) throws IOException{ bw.write(String.valueOf(a)); bw.newLine(); } public void print(long a) throws IOException{ bw.write(String.valueOf(a)); } public void println(double a) throws IOException{ bw.write(String.valueOf(a)); bw.newLine(); } public void print(double a) throws IOException{ bw.write(String.valueOf(a)); } public void print(char a) throws IOException{ bw.write(String.valueOf(a)); } public void println(char a) throws IOException{ bw.write(String.valueOf(a)); bw.newLine(); }}}带权并查集
import java.io.*;import java.math.BigInteger;import java.util.Arrays;import java.util.BitSet;import java.util.HashMap;import java.util.HashSet;import java.util.Iterator;import java.util.LinkedList;import java.util.PriorityQueue;import java.util.Queue;import java.util.StringTokenizer;import java.util.Vector; public class Main{static int find(int x,int[] fa,int[] relation) {if(x==fa[x])return x;else {int f=fa[x];fa[x]=find(fa[x], fa, relation);relation[x]=(relation[x]+relation[f])%3;return fa[x];}}public static void main(String[] args) throws IOException{AReader input=new AReader(); PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out)); int n=input.nextInt(); int k=input.nextInt(); int ans=0; int[] fa=new int[n+1]; int[] relation=new int[n+1]; for(int i=1;i<=n;++i) fa[i]=i; for(int i=1;i<=k;++i) { int op=input.nextInt(); int x=input.nextInt(); int y=input.nextInt(); if(x>n||y>n) { ans++; continue; } if(op==1) { int fx=find(x, fa, relation); int fy=find(y, fa, relation); if(fx==fy) { if(relation[x]!=relation[y]) { ans++; continue; } }else { fa[fx]=fy; relation[fx]=(relation[y]+0-relation[x]+3)%3; } }else { if(x==y) { ans++; continue; } int fx=find(x, fa, relation); int fy=find(y, fa, relation); if(fx==fy) {//0吃1，1吃2，2吃0 if(relation[x]==0&&relation[y]==1|| relation[x]==1&&relation[y]==2|| relation[x]==2&&relation[y]==0)continue; ans++; continue; }else { fa[fx]=fy; relation[fx]=(relation[y]+2-relation[x]+3)%3; } } } out.println(ans); out.flush(); out.close();}staticclass AReader{ BufferedReader bf; StringTokenizer st; BufferedWriter bw; public AReader(){ bf=new BufferedReader(new InputStreamReader(System.in)); st=new StringTokenizer(""); bw=new BufferedWriter(new OutputStreamWriter(System.out)); } public String nextLine() throws IOException{ return bf.readLine(); } public String next() throws IOException{ while(!st.hasMoreTokens()){ st=new StringTokenizer(bf.readLine()); } return st.nextToken(); } public char nextChar() throws IOException{ //确定下一个token只有一个字符的时候再用 return next().charAt(0); } public int nextInt() throws IOException{ return Integer.parseInt(next()); } public long nextLong() throws IOException{ return Long.parseLong(next()); } public double nextDouble() throws IOException{ return Double.parseDouble(next()); } public float nextFloat() throws IOException{ return Float.parseFloat(next()); } public byte nextByte() throws IOException{ return Byte.parseByte(next()); } public short nextShort() throws IOException{ return Short.parseShort(next()); } public BigInteger nextBigInteger() throws IOException{ return new BigInteger(next()); } public void println() throws IOException { bw.newLine(); } public void println(int[] arr) throws IOException{ for (int value : arr) { bw.write(value + " "); } println(); } public void println(int l, int r, int[] arr) throws IOException{ for (int i = l; i <= r; i ++) { bw.write(arr[i] + " "); } println(); } public void println(int a) throws IOException{ bw.write(String.valueOf(a)); bw.newLine(); } public void print(int a) throws IOException{ bw.write(String.valueOf(a)); } public void println(String a) throws IOException{ bw.write(a); bw.newLine(); } public void print(String a) throws IOException{ bw.write(a); } public void println(long a) throws IOException{ bw.write(String.valueOf(a)); bw.newLine(); } public void print(long a) throws IOException{ bw.write(String.valueOf(a)); } public void println(double a) throws IOException{ bw.write(String.valueOf(a)); bw.newLine(); } public void print(double a) throws IOException{ bw.write(String.valueOf(a)); } public void print(char a) throws IOException{ bw.write(String.valueOf(a)); } public void println(char a) throws IOException{ bw.write(String.valueOf(a)); bw.newLine(); }}}