everyone a great god, is write logic problem, why are there so deep search can only choose a starting point for


title background
Given undirected connected graph G and m different colors, use these color for each vertex shader, graph G each vertex with a color, if there is a staining method that each edge of two vertices in G with different colors, says the figure is m colorable, m coloring problem is for a given graph G and m colors, find out all the different coloring,
title description

For a given undirected connected graph G and m different colors, programming calculation chart of all the different coloring,
input format

Line 1 has three positive integer n, k and m, according to a given graph G n vertex and edge k, m colors, vertex Numbers for 1, 2,... , n, the next k lines, each line contains two positive integers, u, v, said one side of the graph G (u, v),
Output format

At the end of the program is running, to calculate the number of different coloring output,

 # include 
using namespace std; 
Int n, k, m, ans; 
Int mp [105] [105]. 
Int color [105]; 
Bool check (int x, int t) {//x node can dye color t 
for(int i=1; i<=n; I++) {
If (mp [x] [I]==1 & amp; & T==color [I]) return false. 
} 
return true; 
} 
Void DFS (int sum) {
If (sum>=n) {
ans++; 
return; 
} 
for(int i=1; i<=n; I++) {//a node 
if(! Color [I]) {//the node without dyeing 
For (int j=1; J<=m; J++) {//choose a color 
If (check (I, j)) {//judge the node can dye the color 
Color [I]=j; 
DFS (sum + 1); 
Color [I]=0;//dyeing 
} 
} 
} 
} 

} 
Int main () {
Cin> N> K> m; 
//adjacency matrix 
for(int i=0; iInt x, y; 
Cin> X> y; 
Mp [x] [y]=1; 
Mp [y] [x]=1; 
} 
DFS (0); 
coutreturn 0; 
} 

CodePudding user response:

"Given a bit of input, a complete single-step tracking (and press Alt + 7 key to view the Call Stack from the inside to the following out of from the inner to outer function Call history) again," is your least-hassle route to understand the working principle of the recursive function!
Recursive function pay attention to the following factors
Exit criteria,
What parameters,
What, the return value is
What are local variables,
What are global variables,
When output,
, will not lead to stack overflow

CodePudding user response:

reference 1/f, zhao teacher reply:

"given a bit of input, a complete single-step tracking (and press Alt + 7 key to view the Call Stack from the inside to the following out of from the inner to outer function Call history) again," is your least-hassle route to understand the working principle of the recursive function!
Recursive function pay attention to the following factors
Exit criteria,
What parameters,
What, the return value is
What are local variables,
What are global variables,
When output,
, will not lead to stack overflow

Thank you zhao four teachers