PROBLEM LINK:
Author: Ildar Gainullin
Tester: Suchan Park
Editorialist: William Lin
DIFFICULTY:
Hard
PREREQUISITES:
Chordal Graph (Perfect Elimination Ordering)
PROBLEM:
Given an undirected graph, direct the edges (or say it’s impossible) such that the graph is acyclic and if there exists two edges u\rightarrow v and u\rightarrow w, then there must exist an edge between v and w.
QUICK EXPLANATION:
Find a perfect elimination ordering of the graph. Direct u to v if u comes before v in the ordering. If the ordering doesn’t exist, then it’s impossible.
EXPLANATION:
Observation 1. If the graph is not chordal, which means that there is some induced cycle with length > 3, then there is no solution. Make sure that you know the precise definition of an induced subgraph. To test your knowledge, make sure you know why a complete graph with any number of nodes does not have any induced cycles with length >3.
Proof
Let u_1, u_2, \dots, u_k be the nodes of some induced cycle (in order) with k > 3. If we direct the edges on this cycle such that all nodes have an out-degree of 1, then we would end up with a directed cycle, which does not satisfy the constraint that the final graph is acyclic. Thus, some nodes will have out-degrees of 0 or 2.
Without loss of generality, u_2 has an out-degree of 2. This means that we have the edges u_2\rightarrow u_1 and u_2\rightarrow u_3, and to satisfy the constraints of the problem, we need an edge between u_1 and u_3. However, since these nodes form an induced cycle and k>3, there is no edge between u_1 and u_3.
Thus, if there exists an induced cycle with length >3, then there is no solution.
Observation 2. If there exists a perfect elimination ordering, then there exists a solution.
Proof
Let p_u be the position of node u in the ordering. For each edge, we will direct u to v if p_u<p_v. The directed graph that is formed is obviously acyclic, because if we have a cycle u_1, u_2, \dots, u_k, it would imply that p_{u_1}<p_{u_2}<\dots <p_{u_k}<p_{u_1}, which doesn’t make sense.
We also need to satisfy the condition that there exists an edge between v and w if there exists two edges u\rightarrow v and u\rightarrow w. This condition is satisfied from the definition of a perfect elimination ordering: All neighbors of u which occur after u in the ordering form a clique (each pair of these neighbors has an edge between them). Since u\rightarrow v and u\rightarrow w, v and w occur after u in the ordering (that’s how we directed the edges), so there will be an edge between v and w.
A chordal graph must have a perfect elimination ordering. So, we just need to find a perfect elimination order of the given graph (or find that it doesn’t exist), which can be done with Lexicographic Breadth-First Search. The time complexity is O(N\log N) or O(N) depending on implementation.
SOLUTIONS:
Setter's Solution
#include <cmath>
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <set>
#include <map>
#include <list>
#include <time.h>
#include <math.h>
#include <random>
#include <deque>
#include <queue>
#include <cassert>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <bitset>
#include <sstream>
#include <chrono>
#include <cstring>
using namespace std;
typedef long long ll;
#ifdef iq
mt19937 rnd(228);
#else
mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
#endif
int main() {
#ifdef iq
freopen("zban_in", "r", stdin);
#endif
ios::sync_with_stdio(0);
cin.tie(0);
int ts;
cin >> ts;
while (ts--) {
int n, m;
cin >> n >> m;
set<pair<int, int> > was;
vector <vector <int> > e(n);
vector <pair <int, int> > t;
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
u--, v--;
was.insert({u, v});
was.insert({v, u});
e[u].push_back(v);
e[v].push_back(u);
t.push_back({u, v});
}
set<pair<int, int> > st;
vector<int> deg(n);
vector<char> f(n, 0);
for (int i = 0; i < n; i++) st.insert({-deg[i], i});
vector<int> vct;
for (int it = 0; it < n; it++) {
int v = st.begin()->second;
st.erase(st.begin());
f[v] = 1;
vct.push_back(v);
for (int to : e[v]) {
if (f[to]) continue;
st.erase({-deg[to], to});
deg[to]++;
st.insert({-deg[to], to});
}
}
reverse(vct.begin(), vct.end());
vector <int> pos(n);
for (int i = 0; i < n; i++) pos[vct[i]] = i;
bool ok = 1;
for (int i = n - 1; i >= 0; i--) {
int v = vct[i];
int mn = n;
for (int to : e[v]) {
if (pos[to] > i) mn = min(mn, pos[to]);
}
for (int to : e[v]) {
if (pos[to] > i) {
int fr = vct[mn];
if (fr > to) swap(fr, to);
ok &= fr == to || was.find({fr, to}) != was.end();
}
}
}
if (!ok) {
cout << "No solution\n";
} else {
vector <int> id(n);
for (int i = 0; i < n; i++) {
id[vct[i]] = i;
}
for (auto c : t) {
if (id[c.first] < id[c.second]) {
cout << '^';
} else {
cout << 'v';
}
}
cout << '\n';
}
}
}
Tester's Solution
//
// Created by ��찬 on 2020/02/22.
//
#include <bits/stdc++.h>
namespace {
const int BUFFER_SIZE = int(1.1e5);
char _buf[BUFFER_SIZE + 10];
int _buf_pos, _buf_len;
char seekChar() {
if(_buf_pos >= _buf_len) {
_buf_len = fread(_buf, 1, BUFFER_SIZE, stdin);
_buf_pos = 0;
}
assert(_buf_pos < _buf_len);
return _buf[_buf_pos];
}
bool seekEof() {
if(_buf_pos >= _buf_len) {
_buf_len = fread(_buf, 1, BUFFER_SIZE, stdin);
_buf_pos = 0;
}
return _buf_pos >= _buf_len;
}
char readChar() {
char ret = seekChar();
_buf_pos++;
return ret;
}
int readInt(int lb, int rb) {
char c = readChar();
int mul = 1;
if(c == '-') {
c = readChar();
mul = -1;
}
assert(isdigit(c));
long long ret = c - '0';
char first_digit = c;
int len = 0;
while(!seekEof() && isdigit(seekChar()) && ++len <= 19) {
ret = ret * 10 + readChar() - '0';
}
ret *= mul;
if(len >= 2) assert(first_digit != '0');
assert(len <= 18);
assert(lb <= ret && ret <= rb);
return (int)ret;
}
void readEoln() {
char c = readChar();
assert(c == '\n');
//assert(c == '\n' || (c == '\r' && readChar() == '\n'));
}
void readSpace() {
char c = readChar();
assert(c == ' ');
}
}
namespace PerfectEliminationOrdering {
// Thank you user zlzmsrhak, I'm too lazy to write code of PEO.
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int MX = 200500;
int lab[MX];
int nxt[MX], prv[MX], sz = 1;
set<int> S[MX];
set<int> G[MX];
int vst[MX];
vector<int> L;
void list_erase(int n){
prv[nxt[n]] = prv[n];
nxt[prv[n]] = nxt[n];
}
void list_insert(int n, set<int> &A){
nxt[++sz] = n; prv[sz] = prv[n];
prv[nxt[sz]] = sz; nxt[prv[sz]] = sz;
swap(S[sz], A);
for(int c : S[sz]) lab[c] = sz;
}
std::vector<int> getOrder(int N, std::vector<std::pair<int,int>> edges)
{
memset(lab, 0, sizeof lab);
memset(nxt, 0, sizeof nxt);
memset(prv, 0, sizeof prv);
memset(vst, 0, sizeof vst);
sz = 1;
L.clear();
for(int i = 0; i < MX; i++) S[i].clear(), G[i].clear();
for(auto it : edges){
int a = it.first;
int b = it.second;
G[a].insert(b);
G[b].insert(a);
}
for(int i = 1; i <= N; i++){
lab[i] = 1;
S[1].insert(i);
} nxt[0] = 1; prv[1] = 0;
for(int i = 1; i <= N; i++){
while(S[nxt[0]].empty()) list_erase(nxt[0]);
int f = nxt[0], v = *S[f].begin();
L.push_back(v);
S[f].erase(S[f].begin()); lab[v] = 0;
if(S[f].empty()) list_erase(f);
map<int, set<int>> tmp;
for(int c : G[v]){
int f = lab[c];
if(!f) continue;
tmp[f].insert(c);
S[f].erase(c);
if(S[f].empty()) swap(tmp[f], S[f]), tmp.erase(f);
}
for(auto e : tmp) list_insert(e.first, e.second);
/*
int cur = 0;
do{
cur = nxt[cur];
printf("%d : ", cur);
for(int c : S[cur]) printf("%d ", c); printf("\n");
}while(cur);
// */
}
reverse(L.begin(), L.end());
for(int i = 0; i < L.size(); i++) vst[L[i]] = i+1;
// for(int c : L) printf("%d ", c); printf("\n");
vst[0] = 1e9;
for(int n : L){
int mn = 0;
for(int c : G[n]) if(vst[c] > vst[n] && vst[c] < vst[mn]) mn = c;
for(int c : G[n]) if(vst[c] > vst[mn] && G[mn].find(c) == G[mn].end()) return {};
}
return L;
}
}
void run() {
int N = readInt(1, 200000);
readSpace();
int M = readInt(1, 200000);
readEoln();
std::set<std::pair<int, int>> _edge_set;
std::vector<std::pair<int, int>> edges;
for(int e = 0; e < M; e++) {
int u = readInt(1, N);
readSpace();
int v = readInt(1, N);
readEoln();
edges.emplace_back(u, v);
if(u > v) std::swap(u, v);
assert(_edge_set.count(std::make_pair(u, v)) == 0);
_edge_set.emplace(u, v);
}
std::vector<int> ord = PerfectEliminationOrdering::getOrder(N, edges);
if(ord.empty()) {
printf("No solution\n");
}else {
std::vector<int> pos(N+1, -1);
for(int i = 0; i < ord.size(); i++) pos[ord[i]] = i;
for(auto it : edges) putchar(pos[it.first] < pos[it.second] ? '^' : 'v');
puts("");
}
}
int main() {
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
#endif
int T = readInt(1, 10);
readEoln();
while(T--) {
run();
}
return 0;
}
Editorialist's Solution
#include <bits/stdc++.h>
using namespace std;
const int mxN=2e5;
int n, m, u[mxN], v[mxN];
struct peo {
vector<int> adj[mxN], a[mxN];
int qu[mxN], pos[mxN], l[mxN], r[mxN], c[mxN];
bool ac(int n) {
iota(qu, qu+n, 0);
iota(pos, pos+n, 0);
memset(l, 0, 4*n);
r[0]=n-1;
memset(c, 0, 4*n);
for(int i=n-1; ~i; --i) {
int u=qu[i];
--r[l[i]];
vector<array<int, 2>> z;
for(int v : adj[u]) {
if(pos[v]>i)
continue;
int lc=l[pos[v]];
z.push_back({r[lc]-c[lc]++, r[lc]});
}
for(int v : adj[u]) {
if(pos[v]>i)
continue;
int np=r[l[pos[v]]]--;
pos[qu[np]]=pos[v];
swap(qu[pos[v]], qu[np]);
l[np]=np-(--c[l[pos[v]]]);
pos[v]=np;
}
for(array<int, 2> a : z)
r[a[0]]=a[1];
int w=-1;
for(int v : adj[u])
if(pos[v]>i&&(w<0||pos[v]<pos[w]))
w=v;
if(~w)
a[w].push_back(u);
}
for(int i=0; i<n; ++i) {
for(int j : adj[i])
c[j]=1;
for(int j : a[i])
for(int k : adj[j])
if(pos[k]>pos[i]&&!c[k])
return 0;
for(int j : adj[i])
c[j]=0;
}
return 1;
}
};
void solve() {
//input
cin >> n >> m;
for(int i=0; i<m; ++i)
cin >> u[i] >> v[i], --u[i], --v[i];
//find the order
peo p;
for(int i=0; i<m; ++i) {
p.adj[u[i]].push_back(v[i]);
p.adj[v[i]].push_back(u[i]);
}
if(!p.ac(n))
cout << "No solution";
else
for(int i=0; i<m; ++i)
cout << "v^"[p.pos[u[i]]<p.pos[v[i]]];
cout << "\n";
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int t;
cin >> t;
while(t--)
solve();
}
Please give me suggestions if anything is unclear so that I can improve. Thanks 