Strongly Connected Directed Graph

Below is an outline of how you can adjust your code so that the final directed graph allows every node to be reachable from every other node (i.e., is strongly connected), under the assumption that your original undirected graph is connected.

The short idea:

1. Run bridge-finding as you already do.
2. For bridges, print both directions (making them effectively “two-way” in the final directed graph).
3. For non-bridge edges, pick a consistent direction (for example, from the node discovered earlier in DFS to the node discovered later).

Why does this work?

• If the original undirected graph is connected, and you make all bridge edges two-way, there is no “single edge” whose orientation can disconnect the graph in the directed sense.
• Non-bridge edges lie on cycles. Once an edge is part of a cycle, orienting it in one direction is enough, because you can still get “back around” that cycle through other edges.
• By directing non-bridge edges consistently (for example, from parent to child in DFS order), you avoid random orientation that could break cycles.

Below is a modified version of your code showing the essential parts. I’ve kept your bridge-detection logic intact, then changed the output section to orient non-bridge edges in a DFS-consistent manner, while making bridge edges two-way.

cpp
#include <bits/stdc++.h>
using namespace std;

static const int MAXN = 1001;

vector<vector<int>> graphAdj(MAXN);
vector<bool> visited(MAXN, false);
vector<int> A(MAXN, 0), B(MAXN, 0);  // A[node] = discovery time, B[node] = low-link
int timer = 1;
vector<pair<int,int>> bridges;

// Standard DFS to find bridges
void dfs(int node, int parent) {
    visited[node] = true;
    A[node] = B[node] = timer++;

    for (auto child : graphAdj[node]) {
        if (child == parent) continue;
        if (visited[child]) {
            // Back edge
            B[node] = min(B[node], A[child]);
        } else {
            // Tree edge
            dfs(child, node);
            B[node] = min(B[node], B[child]);
            
            // If the child's low-link is strictly higher than node's discovery time,
            // then (node, child) is a bridge.
            if (B[child] > A[node]) {
                // Store the bridge with min/max so we can check quickly later.
                bridges.push_back({ min(node, child), max(node, child) });
            }
        }
    }
}

void resetGlobals() {
    // Reset all global structures for each test case
    graphAdj.assign(MAXN, {});
    visited.assign(MAXN, false);
    A.assign(MAXN, 0);
    B.assign(MAXN, 0);
    timer = 1;
    bridges.clear();
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m;
    int caseNum = 1;

    while (true) {
        cin >> n >> m;
        if (!cin || (n == 0 && m == 0)) {
            break;  // end of input
        }

        resetGlobals();

        vector<pair<int,int>> edges(m);
        for (int i = 0; i < m; i++) {
            cin >> edges[i].first >> edges[i].second;
            graphAdj[edges[i].first].push_back(edges[i].second);
            graphAdj[edges[i].second].push_back(edges[i].first);
        }

        // Run DFS from node 1 (assuming 1..n are valid nodes and the graph is connected)
        dfs(1, -1);

        // Put all bridges in a set so we can check quickly if (u, v) is a bridge
        set<pair<int,int>> bridgeSet(bridges.begin(), bridges.end());

        // Print output
        cout << caseNum << "\n\n";

        // For each edge, decide its direction(s)
        for (auto &e : edges) {
            int u = e.first;
            int v = e.second;

            // Sort (u, v) so it matches how we stored them as bridges:
            bool isBridge = bridgeSet.count({min(u, v), max(u, v)});

            if (isBridge) {
                // Print both directions so that removing or flipping this edge
                // cannot “break” connectivity
                cout << u << " " << v << "\n";
                cout << v << " " << u << "\n";
            } else {
                // Non-bridge: pick a single direction.  One simple approach is
                // to compare discovery times A[u] and A[v], and direct from the
                // node that was discovered first to the node that was discovered later.
                // That keeps edges consistent with DFS tree/ back edges.
                if (A[u] < A[v]) {
                    cout << u << " " << v << "\n";
                } else {
                    cout << v << " " << u << "\n";
                }
            }
        }

        cout << "#\n";
        caseNum++;
    }

    return 0;
}

Key Changes / Explanations

1. Bridge Detection
   Your DFS-based bridge detection remains the same.

2. Orientation of Edges

   • Bridge edges become two-way (we print u -> v and v -> u). This ensures that in the directed version, even “critical” edges won’t block returning from one component to another.
   • Non-bridge edges are given a single direction. A common, simple convention is to direct them from the vertex with the smaller discovery time to the vertex with the larger discovery time. That’s what the check if (A[u] < A[v]) ... else ... is doing.

With this scheme:

• The resulting directed graph remains strongly connected if the original undirected graph was connected.
• Bridges won’t break strong connectivity, because they are effectively bi-directional.
• Edges on cycles can safely be oriented one way, because you can still “loop back” around the cycle via other edges (and/or use the two-way bridge edges if needed).

Important: This logic assumes your undirected graph is connected for each test case. If it’s not connected, no orientation of edges can yield a single strongly connected component spanning all nodes.