Create a gist now

Instantly share code, notes, and snippets.

@ctylim /ATR_2C.cpp
Last active Feb 6, 2016

AIM Tech Round 2C
#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <numeric>
#include <functional>
#include <cmath>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <sstream>
#include <string>
#define repd(i,a,b) for (int i=(a);i<(b);i++)
#define rep(i,n) repd(i,0,n)
#define var auto
#define mod 1000000007
#define inf 2147483647
#define mp make_pair
#define pb push_back
typedef long long ll;
using namespace std;
template <typename T>
inline void output(T a, int p) {
if(p){
cout << fixed << setprecision(p) << a << "\n";
}
else{
cout << a << "\n";
}
}
// end of template
int main() {
cin.tie(0);
ios::sync_with_stdio(0);
// source code
int N, M;
cin >> N >> M;
vector<vector<int>> R(N, vector<int>(N, 0));
vector<vector<int>> E(N);
rep(i, M){
int f, t;
cin >> f >> t;
f--, t--;
R[f][t] = R[t][f] = 1;
E[f].pb(t), E[t].pb(f);
}
string s = "";
rep(i, N) s += "b";
vector<vector<int>> L(N);
vector<int> vis(N, 1);
int c = -1;
rep(i, N) repd(j, i + 1, N) if(R[i][j] == 0) L[i].pb(j), L[j].pb(i), c = i, vis[i] = vis[j] = 0;
if (c == -1) {
output("Yes", 0);
output(s, 0);
return 0;
}
queue<int> q; // bfs
q.push(c);
s[c] = 'a';
vis[c] = 1;
while (!q.empty()) {
int t = q.front();
q.pop();
rep(i, L[t].size()){
if (s[L[t][i]] == 'b') {
q.push(L[t][i]);
s[L[t][i]] = (s[t] == 'a') ? 'c' : 'a';
vis[L[t][i]] = 1;
}
}
}
rep(i, N){
if (vis[i] == 0) { // if subgraph is connected
output("No", 0);
return 0;
}
rep(j, L[i].size()){ // are there distinct x-x pairs
if (s[i] == s[L[i][j]]) {
output("No", 0);
return 0;
}
}
rep(j, E[i].size()){
if (abs(s[i] - s[E[i][j]]) == 2) { // are there a-c edges
output("No", 0);
return 0;
}
}
}
output("Yes", 0);
output(s, 0);
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment