所需的最小颜色，以使边缘形成循环不会具有相同的颜色

Question

给定一个带 V 顶点和 E 边且无自环和多个边的有向图，任务是找到所需的最少颜色数，以使相同颜色的边不会形成循环，并找到每个边的颜色。
例子：

Input: V = {1, 2, 3}, E = {(1, 2), (2, 3), (3, 1)}
Output: 2
1 1 2

Explanation:
In the above given graph it forms only one cycle,
that is Vertices connecting 1, 2, 3 forms a cycle
Then the edges connecting 1->2 or 2->3 or 3->1 can be colored
with a different color such that edges forming cycle don’t have same color
Input: V = {1, 2, 3, 4, 5}, E = {(1, 2), (1, 3), (2, 3), (2, 4), (3, 4), (4, 5), (5, 3)}
Output: 2
Colors of Edges – 1 1 1 1 1 1 2
Explanation:
In the above given graph it forms only one cycle,
that is Vertices connecting 3, 4, 5 forms a cycle
Then the edges connecting 5->3 or 4->5 or 3->4 can be colored
with a different color such that edges forming cycle don’t have same color
Final Colors of the Edges –
{1: 1, 2: 1, 3: 1, 4: 1, 5: 1, 6: 1, 7: 2}
The above array denotes the pairs as – Edge : Color Code

方法：想法是找到图中的循环，这可以在图的 DFS 的帮助下完成，在该循环中，当用新边再次访问已访问的节点时，该边将用另一种颜色进行着色否则，如果没有循环，则所有边缘只能用一种颜色上色。
算法：

• 用颜色 1 标记每个边缘，将每个顶点标记为未访问。
• 使用图的 DFS 遍历遍历图并标记访问的节点。
• 如果已经访问了一个节点，则连接顶点的边将标记为用颜色 2 着色。
• 访问所有顶点时，打印边缘的颜色。

举例说明：
示例 1 的详细空运行

Current Vertex	Current Edge	Visited Vertices	Colors of Edges	Comments
1	1–>2	{1}	{1: 1, 2: 1, 3: 1}	Node 1 is marked as visited and Calling DFS for node 2
2	2–>3	{1, 2}	{1: 1, 2: 1, 3: 1}	Node 2 is marked as visited and Calling DFS for node 3
3	3–>1	{1, 2}	{1: 1, 2: 1, 3: 2}	As 1 is already Visited color of Edge 3 is changed to 2

下面是上述方法的实现：

C++

// C++ implementation to find the
// minimum colors required to
// such that edges forming cycle
// don't have same color
 
#include 
using namespace std;
 
const int n = 5, m = 7;
 
// Variable to store the graph
vector<pair<int, int=""> > g[m];
 
// To store that the
// vertex is visited or not
int col[n];
 
// Boolean Value to store that
// graph contains cycle or not
bool cyc;
 
// Variable to store the color
// of the edges of the graph
int res[m];
 
// Function to traverse graph
// using DFS Traversal
void dfs(int v)
{
    col[v] = 1;
     
    // Loop to iterate for all
    // edges from the source vertex
    for (auto p : g[v]) {
        int to = p.first, id = p.second;
         
        // If the vertex is not visited
        if (col[to] == 0)
        {
            dfs(to);
            res[id] = 1;
        }
         
        // Condition to check cross and
        // forward edges of the graph
        else if (col[to] == 2)
        {
            res[id] = 1;
        }
         
        // Presence of Back Edge
        else {
            res[id] = 2;
            cyc = true;
        }
    }
    col[v] = 2;
}
 
// Driver Code
int main()
{
    g[0].push_back(make_pair(1, 0));
    g[0].push_back(make_pair(2, 1));
    g[1].push_back(make_pair(2, 2));
    g[1].push_back(make_pair(3, 3));
    g[2].push_back(make_pair(3, 4));
    g[3].push_back(make_pair(4, 5));
    g[4].push_back(make_pair(2, 6));
     
    // Loop to run DFS Traversal on
    // vertex which is not visited
    for (int i = 0; i < n; ++i) {
        if (col[i] == 0)
        {
            dfs(i);
        }
    }
    cout << (cyc ? 2 : 1) << endl;
     
    // Loop to print the
    // colors of the edges
    for (int i = 0; i < m; ++i) {
        cout << res[i] << ' ';
    }
    return 0;
}</pair<int,>

---

Java

// Java implementation to find the
// minimum colors required to
// such that edges forming cycle
// don't have same color
import java.util.*;
 
class GFG{
  
static int n = 5, m = 7;
static class pair
{
    int first, second;
    public pair(int first, int second) 
    {
        this.first = first;
        this.second = second;
    }   
}
 
// Variable to store the graph
static Vector []g = new Vector[m];
  
// To store that the
// vertex is visited or not
static int []col = new int[n];
  
// Boolean Value to store that
// graph contains cycle or not
static boolean cyc;
  
// Variable to store the color
// of the edges of the graph
static int []res = new int[m];
  
// Function to traverse graph
// using DFS Traversal
static void dfs(int v)
{
    col[v] = 1;
      
    // Loop to iterate for all
    // edges from the source vertex
    for (pair  p : g[v]) {
        int to = p.first, id = p.second;
          
        // If the vertex is not visited
        if (col[to] == 0)
        {
            dfs(to);
            res[id] = 1;
        }
          
        // Condition to check cross and
        // forward edges of the graph
        else if (col[to] == 2)
        {
            res[id] = 1;
        }
          
        // Presence of Back Edge
        else {
            res[id] = 2;
            cyc = true;
        }
    }
    col[v] = 2;
}
  
// Driver Code
public static void main(String[] args)
{
    for(int i= 0; i < m; i++)
        g[i] = new Vector();
    g[0].add(new pair(1, 0));
    g[0].add(new pair(2, 1));
    g[1].add(new pair(2, 2));
    g[1].add(new pair(3, 3));
    g[2].add(new pair(3, 4));
    g[3].add(new pair(4, 5));
    g[4].add(new pair(2, 6));
      
    // Loop to run DFS Traversal on
    // vertex which is not visited
    for (int i = 0; i < n; ++i) {
        if (col[i] == 0)
        {
            dfs(i);
        }
    }
    System.out.print((cyc ? 2 : 1) +"\n");
      
    // Loop to print the
    // colors of the edges
    for (int i = 0; i < m; ++i) {
        System.out.print(res[i] +" ");
    }
}
}
 
// This code is contributed by sapnasingh4991

---

Python3

# Python3 implementation to find the
# minimum colors required to
# such that edges forming cycle
# don't have same color
  
n = 5
m = 7;
  
# Variable to store the graph
g = [[] for i in range(m)]
  
# To store that the
# vertex is visited or not
col = [0 for i in range(n)];
  
# Boolean Value to store that
# graph contains cycle or not
cyc = True
  
# Variable to store the color
# of the edges of the graph
res = [0 for i in range(m)];
  
# Function to traverse graph
# using DFS Traversal
def dfs(v):
 
    col[v] = 1;
      
    # Loop to iterate for all
    # edges from the source vertex
    for p in g[v]:
         
        to = p[0]
        id = p[1];
          
        # If the vertex is not visited
        if (col[to] == 0):
         
            dfs(to);
            res[id] = 1;
         
        # Condition to check cross and
        # forward edges of the graph
        elif (col[to] == 2):
         
            res[id] = 1;
          
        # Presence of Back Edge
        else:
            res[id] = 2;
            cyc = True;
 
    col[v] = 2;
 
# Driver Code
if __name__=='__main__':
     
    g[0].append([1, 0]);
    g[0].append([2, 1]);
    g[1].append([2, 2]);
    g[1].append([3, 3]);
    g[2].append([3, 4]);
    g[3].append([4, 5]);
    g[4].append([2, 6]);
      
    # Loop to run DFS Traversal on
    # vertex which is not visited
    for i in range(n):
     
        if (col[i] == 0):
         
            dfs(i);
         
    print(2 if cyc else 1)
      
    # Loop to print the
    # colors of the edges
    for i in range(m):
        print(res[i], end=' ')
  
# This code is contributed by rutvik_56

---

C#

// C# implementation to find the
// minimum colors required to
// such that edges forming cycle
// don't have same color
using System;
using System.Collections.Generic;
 
class GFG{
   
static int n = 5, m = 7;
class pair
{
    public int first, second;
    public pair(int first, int second) 
    {
        this.first = first;
        this.second = second;
    }   
}
  
// Variable to store the graph
static List []g = new List[m];
   
// To store that the
// vertex is visited or not
static int []col = new int[n];
   
// Boolean Value to store that
// graph contains cycle or not
static bool cyc;
   
// Variable to store the color
// of the edges of the graph
static int []res = new int[m];
   
// Function to traverse graph
// using DFS Traversal
static void dfs(int v)
{
    col[v] = 1;
       
    // Loop to iterate for all
    // edges from the source vertex
    foreach (pair  p in g[v]) {
        int to = p.first, id = p.second;
           
        // If the vertex is not visited
        if (col[to] == 0)
        {
            dfs(to);
            res[id] = 1;
        }
           
        // Condition to check cross and
        // forward edges of the graph
        else if (col[to] == 2)
        {
            res[id] = 1;
        }
           
        // Presence of Back Edge
        else {
            res[id] = 2;
            cyc = true;
        }
    }
    col[v] = 2;
}
   
// Driver Code
public static void Main(String[] args)
{
    for(int i= 0; i < m; i++)
        g[i] = new List();
    g[0].Add(new pair(1, 0));
    g[0].Add(new pair(2, 1));
    g[1].Add(new pair(2, 2));
    g[1].Add(new pair(3, 3));
    g[2].Add(new pair(3, 4));
    g[3].Add(new pair(4, 5));
    g[4].Add(new pair(2, 6));
       
    // Loop to run DFS Traversal on
    // vertex which is not visited
    for (int i = 0; i < n; ++i) {
        if (col[i] == 0)
        {
            dfs(i);
        }
    }
    Console.Write((cyc ? 2 : 1) +"\n");
       
    // Loop to print the
    // colors of the edges
    for (int i = 0; i < m; ++i) {
        Console.Write(res[i] +" ");
    }
}
}
  
// This code is contributed by PrinciRaj1992

---

输出：

2
1 1 1 1 1 1 2

性能分析：

• 时间复杂度：与上述方法一样，图的 DFS 遍历需要 O(V + E) 时间，其中 V 表示顶点数，E 表示边数。因此，时间复杂度将为O(V + E) 。
• 辅助空间： O(1)。