Codeforces AIM Tech Round Div2 C

問題

codeforces.com

考察

入力としてどの頂点がどの頂点つながっているかを与えられる。

頂点xと頂点yがつながっているということは頂点xと頂点yに対応する文字が隣接しているということ。

逆に頂点xと頂点yがつながっていないということは必ずその2つの頂点に対応する文字が'a'と'c',または'c'と'a'ということ。

なので、つながっていない頂点同士にそれぞれ'a'か'c'を当てはめて,それ以外の頂点には'b'を当てはめて,最終的に「頂点同士がつながっていないのに文字は隣接している場合」と
「頂点同士はつながっているのに,それぞれの文字が'a'と'c'の場合」はNoであり,それ以外の場合はYesと出力すればよい。

ソースコード

import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.NoSuchElementException;
 
import java.util.*;
 
public class Main {
	int N,M;
	int[] kind;
	boolean[][] connect;
	public void solve(){
		N = nextInt();
		M = nextInt();
		connect = new boolean[N][N];
		for(int i = 0;i < M;i++){
			int u = nextInt() - 1;
			int v = nextInt() - 1;
			connect[u][v] = connect[v][u] = true;
		}
		
		kind = new int[N];
		Arrays.fill(kind,1);
		for(int i = 0;i < N;i++){
			for(int j = i + 1;j < N;j++){
				if(!connect[i][j]){
					if(kind[i] == 1){
						kind[i] = 0;
						kind[j] = 2;
					}else if(kind[i] == 0){
						kind[j] = 2;
					}else{
						kind[j] = 0;
					}
				}
			}
		}
		for(int i = 0;i < N;i++){
			for(int j = i + 1;j < N;j++){
				if(!connect[i][j] && Math.abs(kind[i] - kind[j]) <= 1){
					out.println("No");
					return;
				}
				
				if(connect[i][j] && Math.abs(kind[i] - kind[j]) >= 2){
					out.println("No");
					return ;
				}
			}
		}
		
		out.println("Yes");
		for(int i = 0;i < N;i++){
			out.print((char)(kind[i] + 'a'));
		}
		out.println();
	}
 
	public static void main(String[] args) {
		out.flush();
		new Main().solve();
		out.close();
	}
 
	/* Input */
	private static final InputStream in = System.in;
	private static final PrintWriter out = new PrintWriter(System.out);
	private final byte[] buffer = new byte[2048];
	private int p = 0;
	private int buflen = 0;
 
	private boolean hasNextByte() {
		if (p < buflen)
			return true;
		p = 0;
		try {
			buflen = in.read(buffer);
		} catch (IOException e) {
			e.printStackTrace();
		}
		if (buflen <= 0)
			return false;
		return true;
	}
 
	public boolean hasNext() {
		while (hasNextByte() && !isPrint(buffer[p])) {
			p++;
		}
		return hasNextByte();
	}
 
	private boolean isPrint(int ch) {
		if (ch >= '!' && ch <= '~')
			return true;
		return false;
	}
 
	private int nextByte() {
		if (!hasNextByte())
			return -1;
		return buffer[p++];
	}
 
	public String next() {
		if (!hasNext())
			throw new NoSuchElementException();
		StringBuilder sb = new StringBuilder();
		int b = -1;
		while (isPrint((b = nextByte()))) {
			sb.appendCodePoint(b);
		}
		return sb.toString();
	}
 
	public int nextInt() {
		return Integer.parseInt(next());
	}
 
	public long nextLong() {
		return Long.parseLong(next());
	}
 
	public double nextDouble() {
		return Double.parseDouble(next());
	}
}