The final graph will have only directed edges and should be
acyclic. For a directed graph, having no cycles is equivalent to
being able to pick an ordering a[i] of the vertices
such that anytime there is an edge from a[i] to
a[j] we have i < j. (Think of this as
lining the vertices up left to right such that all directed edges
point to the right.) This is called a topological ordering.
If a directed graph has a topological ordering, it must be acyclic,
and we can find some topological ordering for any directed acyclic
graph.
In the input graph, some of the edges are directed and some are
undirected. However, we know that the directed edges do not form
a cycle. Thus, we can find a topological ordering a[i]
of the vertices with respect to the directed edges. (That is, we
can line up the vertices such that all of the directed edges point
to the right.) Then, if an undirected edge goes between a[i]
and a[j], we direct it from a[i] to
a[j] if i < j and from a[j]
to a[i] if j < i. (That is, we direct
the undirected edges so that they all point to the right too.) Our
new graph will have no cycles. (Because all of the edges now point
to the right.)
To find the original topological ordering of the graph with respect to the directed edges, we can use one of a couple of standard algorithms. Here's one. Maintain the number of directed edges coming into each vertex. Since the graph has no cycles, there must be some vertex with no edges coming in. We process that vertex in the following way: place it at the start of our ordering, then delete that vertex and all of its outgoing edges. If, by deleting those edges, we created a vertex which now has no incoming edges, process those vertices recursively. (Note that since N is large, there is a danger of overflowing the run-time stack, so we may need to use our own stack rather than explicitly calling a function recursively.) After a single loop through all of the vertices in which we process all vertices which originally had no incoming edges, we will have recursively processed the entire graph and put the vertices in order.
#include <assert.h>
#include <string.h>
#include <stdio.h>
const int MAXN = 500000 + 10;
const int MAXM = 500000 + 10;
int n,m1,m2;
int outdeg[MAXN];
int indeg[MAXN];
int *edge[MAXN];
int edge_array[MAXM];
int pos[MAXN];
int mystack[MAXN];
bool v[MAXN];
int main () {
FILE* fin = fopen ("dizzy.in", "r");
fscanf (fin, "%d %d %d", &n, &m1, &m2);
for (int i = 0; i < n; ++i) {
outdeg[i] = 0;
}
for (int i = 0; i < m1; ++i) {
int a,b;
fscanf (fin, "%d %d", &a, &b);
--a; --b; // 1 -> 0
++outdeg[a];
}
fclose (fin);
edge[0] = &edge_array[0];
for (int i = 1; i < n; ++i) {
edge[i] = edge[i-1] + outdeg[i-1];
}
fin = fopen ("dizzy.in", "r");
fscanf (fin, "%d %d %d", &n, &m1, &m2);
for (int i = 0; i < n; ++i) {
indeg[i] = 0;
outdeg[i] = 0;
}
for (int i = 0; i < m1; ++i) {
int a,b;
fscanf (fin, "%d %d", &a, &b);
--a; --b; // 1 -> 0
edge[a][outdeg[a]] = b;
++outdeg[a];
++indeg[b];
}
memset (v, false, sizeof (bool)*n);
int p = 0;
for (int i = 0; i < n; ++i) {
if (v[i] || indeg[i] != 0) continue;
v[i] = true;
int sp = 0;
mystack[sp++] = i;
while (sp != 0) {
int x = mystack[--sp];
pos[x] = p++;
for (int j = 0; j < outdeg[x]; ++j) {
int y = edge[x][j];
--indeg[y];
if (indeg[y] == 0) {
assert (!v[y]);
v[y] = true;
mystack[sp++] = y;
}
}
}
}
FILE* fout = fopen ("dizzy.out", "w");
for (int i = 0; i < m2; ++i) {
int a,b;
fscanf (fin, "%d %d", &a, &b);
--a; --b; // 1 -> 0
if (pos[a] < pos[b]) {
fprintf (fout, "%d %d\n", 1+a, 1+b);
} else {
fprintf (fout, "%d %d\n", 1+b, 1+a);
}
}
fclose (fout);
fclose (fin);
return (0);
}