图论练习4

内容：染色划分，带权并查集，扩展并查集

Arpa’s overnight party and Mehrdad’s silent entering

题目链接

题目大意

$2n$ 个点围成一圈，分为 $n$ 对，对内两点不同染色
同时，相邻3个点之间必须有两个点不同染色
问构造出一种染色方案

解题思路

将每对进行的连边看作一类边
将为满足相邻3个点必须有两个点不同染色的边，看作二类边
满足构造方案，即将 $2n$ 个点形成一个二分图，无奇环
对于只有一类边，形不成环，端点不同
对于二类边与一类边组合才能形成环
将二类边定义为 $2_i\leftrightarrow 2_i+1$
成环的情况只能，如下图
由于一类边不可能相连，中间必然是二类边，一类边交换，所以环上的点数为二类边的总点数，一定为偶数，只能形成偶环，构造成立
利用带权并查集实现


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();}}
}

食物链

题目链接

题目大意

$n$ 个点， $k$ 对关系
每个点可能为 $A/B/C$ 类，它们之间满足 $A$ 吃 $B$ ， $B$ 吃 $C$ ， $C$ 吃 $A$
$k$ 对关系中， $1,x,y$ 表示 $x,y$ 同类， $2,x,y$ 表示 $x$ 吃 $y$
依次处理 $k$ 对关系，若当前关系与之前的关系矛盾，则视为错误
$x>n,y>n,(2,x,y)x=y$ （自己吃自己），均视为错误
问有多少对错误

解题思路

对 $n$ 个点进行 $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) {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->xAans++;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吃xans++;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吃0if(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();}}
}