Given edges in directed graph, if each edge is assigned to one node what is maximum number of edges-CodePudding

Say there is a directed graph with 5 nodes with 4 edges in the format (a, b) where there is an edge from a to b.

edges = [(1, 2), (4, 1), (4, 3), (3, 5)]

Each edge will be assigned one of its node values, for example edge 1 (the (1, 2) edge) may be assigned the node 1 or 2. It will try to be assigned the first value, 1, and if that number was already assigned it will try to be assigned node 2. If 2 was already taken, edge 1 has no value. Find the maximum edges that are assigned some value and also a valid sequence of choosing which edges are assigned.

My approach pseudocode

function dfs (current node)
    if seen contains current node
        return
    for next node : graph[current node]
        if current node was not assigned to any edge before
            assign current node to the id of edge (current_node, next_node)
        if current node was assigned but next node was not
            assign next node to the id of edge (current_node, next_node)
        dfs(next_node)
seen = hashest
for num:all node
    if seen does not contain num and current node was not assigned to any edge
        dfs(num)

Although this works sometimes, it does not always find the maximum amount of edges. Sometimes, dfs ing from node 1 to n in order is not the optimal approach, or at least that is what I found using this code. Is there a constant time implementation or do I have to search by starting at different nodes? For example, using my code, lets say I started at edge 4, (3, 5). According to my algorithm, edge (3,5) is assigned node 3. Then, say I started at edge 2, or (4, 1). Then, edge 2 is assigned node 4, and since edge 1, (1, 2), is a neighbor it is assigned node 1. However, this means edge (4,3) was not assigned to any node. And, it was in fact possible to assign nodes to all.

CodePudding user response：

If the graph is connected ( all nodes can be reached from one of the nodes ) then the maximum number of edges that can be assigned a number is min( E, N ) where N is the number of nodes and E the number of edges

The algorithm is:

Copy graph, making all edges bidirectional
LOOP over edges in copy by using DFS
   IF src node unassigned, assign src to edge
   ELSE assign dst to edge

In your example suppose the 1-2 edge is looked at first, the result will be

1 - 2 < 1
1 - 4 < 4  ( 1 was assigned )
4 - 3 < 3
3 - 5 < 5

But if 1-4 is looked at first

1 - 4 < 1
4 - 3 < 4
3 - 5 < 3
1 - 2 < 2 ( 1 was assigned )

BTW, if the graph is NOT connected, then the algorithm can be applied to each component.