Universal sink

Challenge

int has_universal_sink(const int *adj,int n);

A universal sink is a vertex with out-degree 0 that every other vertex points to. Return 1 if one exists, else 0.

Input format

adj n×n directed 0/1.

Output format

1 if a sink exists, else 0.

Constraints

Single vertex is a sink.

Starter code

#include <stddef.h>
/* Return 1 if the directed graph has a universal sink: a node with out-degree 0 that every OTHER node points to. */
int has_universal_sink(const int *adj,int n){ (void)adj;(void)n; return 0; }

Common mistakes

Forgetting the sink must have no outgoing edges, or that all others must point to it.

Edge cases to handle

Single vertex → 1; a cycle → 0.

Background lessons

• Graph properties