/**
* Process vertices in decreasing order of a, in blocks of sqrt(n) at a
* time. Build a disjoint set forest using vertices that are present in the
* graph for the entire block, then for each color test connectivity on that
* forest plus other relevant vertices.
*
* Author: Catalin Francu
**/
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#define MAX_N 150000
#define MAX_M 200000
#define NIL -1
typedef struct {
int node, next;
} cell;
typedef struct {
int u, v;
} edge;
/* color data */
int a[MAX_N], b[MAX_N];
int alist[MAX_N], blist[MAX_N]; /* head pointers of color lists */
cell c[2 * MAX_N]; /* buffer for color lists */
int numColors;
/* graph data */
edge e[MAX_M]; /* edge list */
int dsf[MAX_N]; /* disjoint set forest */
int m, n;
/* block-level graph data */
edge be[MAX_M]; /* edge list */
int bm; /* number of edges */
int bd[MAX_N]; /* disjoint set forest */
/* other data */
int seen[MAX_N + 1]; /* for counting things */
int edgeCmp(const void* x, const void* y) {
return a[((edge*)y)->v] - a[((edge*)x)->v];
}
/* renumber colors to eliminate gaps */
void renumberColors() {
int i, u;
numColors = 0;
for (i = 1; i <= n; i++) {
seen[i] = 0;
}
for (u = 0; u < n; u++) {
seen[a[u]] = seen[b[u]] = 1;
}
for (i = 1; i <= n; i++) {
if (seen[i]) {
seen[i] = numColors++;
}
}
for (u = 0; u < n; u++) {
a[u] = seen[a[u]];
b[u] = seen[b[u]];
}
/* reset seen[] for connectivity testing */
for (i = 0; i < n; i++) {
seen[i] = numColors;
}
}
/* read colors and build vertex lists for every color */
void readColors() {
int i, u;
for (u = 0; u < n; u++) {
scanf("%d", &a[u]);
}
for (u = 0; u < n; u++) {
scanf("%d", &b[u]);
}
renumberColors();
int ptr = 0;
for (i = 0; i < numColors; i++) {
alist[i] = blist[i] = NIL;
}
for (u = 0; u < n; u++) {
c[ptr].node = u;
c[ptr].next = alist[a[u]];
alist[a[u]] = ptr++;
c[ptr].node = u;
c[ptr].next = blist[b[u]];
blist[b[u]] = ptr++;
}
}
/* read edges and sort them by min(a[u], a[v]) (decreasing) */
void readGraph() {
int i, u, v;
for (i = 0; i < m; i++) {
scanf("%d%d", &u, &v);
u--; v--;
if (a[u] < a[v]) {
int tmp = u;
u = v;
v = tmp;
}
e[i] = (edge) { u, v };
}
qsort(e, m, sizeof(edge), edgeCmp);
}
inline int dsfFind(int* f, int x) {
int root = x;
do {
root = f[root];
} while (f[root] != root);
/* path compression */
while (f[x] != root) {
int tmp = f[x];
f[x] = root;
x = tmp;
}
return root;
}
inline void dsfUnion(int* f, int x, int y) {
f[dsfFind(f, x)] = dsfFind(f, y);
}
/* given a high color, find a corresponding low color so that the interval */
/* has O(sqrt(n)) vertices */
int findBlock(int hi) {
int lo = hi + 1, size = 2 * sqrt(n);
while (lo > 0 && size >= 0) {
lo--;
/* count vertices covered by this new lo */
for (int p = alist[lo]; p != NIL; p = c[p].next) {
size--;
}
for (int p = blist[lo]; p != NIL; p = c[p].next) {
int u = c[p].node;
size -= (a[u] > hi);
}
}
return lo;
}
/* build disjoint set structures limited to edges between vertices */
/* of the form a > hi, b < lo */
void buildSets(int lo, int hi) {
for (int u = 0; u < n; u++) {
dsf[u] = u;
}
int i = 0;
while (i < m && a[e[i].v] > hi) { /* then a[u] and a[v] are both > hi */
if (b[e[i].u] < lo && b[e[i].v] < lo) {
dsfUnion(dsf, e[i].u, e[i].v);
}
i++;
}
}
/* collect (a) edges within the current block and (b) edges from the current */
/* block to the inner rectangle */
void collectBlockEdges(int lo, int hi) {
bm = 0;
int i = 0;
while (i < m && a[e[i].v] >= lo) {
int u = e[i].u, v = e[i].v;
/* both are in the current block, but not both are in the inner rectangle */
if (b[u] <= hi &&
b[v] <= hi &&
(a[v] <= hi || b[u] >= lo || b[v] >= lo)) {
be[bm++] = (edge) { dsfFind(dsf, u), dsfFind(dsf, v) };
}
i++;
}
}
/* Disjoint set forests for the current color. These need to be computed */
/* carefully in order to explore only O(sqrt(n)) vertices and avoid */
/* overflowing into the entire graph. */
void buildBlockSets(int col) {
/* initialize endpoints of collected edges plus any isolated vertices */
for (int i = 0; i < bm; i++) {
bd[be[i].u] = be[i].u;
bd[be[i].v] = be[i].v;
}
for (int p = alist[col]; p != NIL; p = c[p].next) {
bd[c[p].node] = c[p].node;
}
for (int p = blist[col]; p != NIL; p = c[p].next) {
bd[c[p].node] = c[p].node;
}
/* union-find on valid edges for this color */
int i = 0;
while (i < bm && a[be[i].v] >= col) {
if (b[be[i].u] <= col && b[be[i].v] <= col) {
dsfUnion(bd, be[i].u, be[i].v);
}
i++;
}
}
/* true if all vertices having b = col are reachable from vertices */
/* having a = col */
int satisfiable(int col) {
/* for all u having a[u] = col, mark u's component as seen */
for (int p = alist[col]; p != NIL; p = c[p].next) {
seen[dsfFind(bd, c[p].node)] = col;
}
/* for all v having b[v] = col, ensure that v's component is seen */
int p = blist[col];
while (p != NIL && seen[dsfFind(bd, c[p].node)] == col) {
p = c[p].next;
}
return (p == NIL);
}
int main() {
int numTests;
scanf("%d", &numTests);
while (numTests--) {
scanf("%d%d", &n, &m);
readColors();
readGraph();
int hi = numColors - 1, ok = 1;
while (hi >= 0 && ok) {
/* compute block-level data */
int lo = findBlock(hi);
buildSets(lo, hi);
collectBlockEdges(lo, hi);
/* check that all colors hi...lo are satisfiable */
while (hi >= lo && ok) {
buildBlockSets(hi);
ok = satisfiable(hi);
hi--;
}
}
printf("%d\n", ok);
}
return 0;
}
Compilation message
colors.c: In function 'readColors':
colors.c:80:5: warning: ignoring return value of 'scanf', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &a[u]);
^~~~~~~~~~~~~~~~~~
colors.c:83:5: warning: ignoring return value of 'scanf', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &b[u]);
^~~~~~~~~~~~~~~~~~
colors.c: In function 'readGraph':
colors.c:108:5: warning: ignoring return value of 'scanf', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &u, &v);
^~~~~~~~~~~~~~~~~~~~~
colors.c: In function 'main':
colors.c:241:3: warning: ignoring return value of 'scanf', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &numTests);
^~~~~~~~~~~~~~~~~~~~~~
colors.c:244:5: warning: ignoring return value of 'scanf', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &n, &m);
^~~~~~~~~~~~~~~~~~~~~
/tmp/ccK1f1U9.o: In function `findBlock':
colors.c:(.text+0x3ee): undefined reference to `sqrt'
collect2: error: ld returned 1 exit status
