Deep search + backtracking

L2-2 Trace the source of the virus (25 branch )

Viruses are prone to mutation . A virus can mutate to produce several mutated strains , These mutated viruses may be induced to mutate to produce second-generation mutations , So it continues to change .

Now let's give some variation relationships between viruses , Ask you to find the longest variation chain .

It is assumed that all the variations given here are caused by mutations , Do not consider the complex problem of gene recombination and mutation —— That is, each virus is mutated from the only virus , And there is no cyclic variation .

Input format ：

Input gives a positive integer in the first line N（≤10^​4 ）, That is, the total number of virus types . So we took all the viruses from 0 To N−1 Number . And then N That's ok , Each line describes the variation of a virus in the following format ：

k Mutant 1 …… Mutant k

among k Is the number of species of mutant strains produced by the virus , Followed by the number of each variant . The first i The corresponding number of the line is i The virus of （0≤i<N）. The problem is to ensure that there is and only one source of the virus .

Output format ：

First, output the length of the longest variation chain from the source .

In the second line, output the longest variation chain from the source , Between numbers 1 Space separation , There must be no extra space at the beginning and end of the line . If the longest chain is not unique , Then the minimum sequence is output .

notes ： We call it sequence { a​1​​ ,⋯,a​n } Ratio sequence { b​1​​ ,⋯,b​n​​ } “ Small ”, If there is 1≤k≤n Satisfy a​i​​ =b​i​​ For all i<k establish , And a​k​​ <b​k​​ .

sample input ：

10
3 6 4 8
0
0
0
2 5 9
0
1 7
1 2
0
2 3 1

sample output ：

4
0 4 9 1

#include<iostream>
using namespace std;
int map[10000][10000] = {
     0 };// Build a graph to store the connections between each virus 
int dog[10000] = {
     0 };// Pathfinder , Judge whether the point passes through 
int way[10000] = {
     0 };// Record the longest viral variation 
int now[10000] = {
     0 };// Record the current virus mutation path 
int head[10000] = {
     0 };// Record the source of the virus 
int maxpass = 0;// Record the maximum number of variations 
int n;// Number of viruses 
void DFS(int x, int pass);
void ntow(int pass);// take now The data of the array is assigned to way Array 
int main()
{
    
	int pass;// Record the current number of virus variants 
	cin >> n;
	int i = 0;
	int a;
	int data;
	for (i = 0; i < n; i++) {
    
		cin >> data;
		for (int j = 0; j < data; j++) {
    
			cin >> a;
			map[i][a] = 1;// Build a directed graph 
			head[a] = 1;// The source does not appear in the mutated data , So finally for 0 The point where the virus originated 
		}
	}
	for (i = 0; i < n; i++) {
    
		if (!head[i]) {
    // Find the source of the virus 
			pass = 0;
			DFS(i, pass);
		}
	}
	cout << maxpass << endl;
	for (i = 0; i < maxpass; i++) {
    
		if (!i)cout << way[i];
		else cout << " " << way[i];
	}
	if (!maxpass) cout << "0" << endl;
}
void DFS(int x, int pass) {
    
	dog[x] = 1;
	int i = 0;
	now[pass] = x;
	pass++;
	for (i = 0; i < n; i++) {
    
		if (map[x][i] && !dog[i]) {
    
			DFS(i, pass);
		}
	}
	if (pass > maxpass) ntow(pass);// Store the largest virus data in by backtracking way Array 
}
void ntow(int pass)
{
    
	int i = 0;
	for (i = 0; i < pass; i++) {
    
		way[i] = now[i];
	}
	maxpass = pass;
}

6-2- Depth-first search Underground labyrinth exploration (30 branch ）

Tunnel warfare was during the Anti Japanese war , In the North China Plain, the Anti Japanese army and people used tunnels to fight against the Japanese aggressors . Tunnel network is house to house 、 Street to street 、 Village to village underground works , As shown in the figure below .

While reviewing the arduous war life of our predecessors , I really admire their intelligence . In this era of peaceful development , For most people , Exploring the underpass may just be an entertainment or puzzle game . This experimental case takes the exploration of underground passage maze as the content .

Suppose there is an underground passage maze , Its passages are straight , And all the intersections of the channel （ Include the endpoint of the channel ） There is a light and a switch on the . How do you light all the lights in the maze from a certain starting point and return to the starting point ？

Input format :

The first line of input gives three positive integers , Respectively represent the number of nodes in the underground maze N（1<N≤1000, Represents all intersections and endpoints of the channel ）、 Number of edges M（≤3000, Indicates the number of channels ） And exploration start node number S（ Node slave 1 To N Number ）. And then M Row correspondence M side （ passageway ）, Each line gives a pair of positive integers , They are the numbers of two nodes directly connected by the edge .

Output format :

If you can light up the lights of all nodes , Output from S Start with S The ending sequence containing all nodes , Adjacent nodes in the sequence must have edges （ passageway ）; Otherwise, although the lights of all nodes cannot be lit , But it still outputs the node sequence that lights up some lights , The final output 0, At this point, it means that the maze is not a connected graph .

Because the node sequence traversed by depth first is not unique , In order to make the output unique , We agree to access in the order of node small number first （ Lighting ）. After lighting all the lights that can be lit , Return to the starting point by returning the same way .

sample input 1:

6 8 1
1 2
2 3
3 4
4 5
5 6
6 4
3 6
1 5

sample output 1:

1 2 3 4 5 6 5 4 3 2 1

sample input 2:

6 6 6
1 2
1 3
2 3
5 4
6 5
6 4

sample input 2:

6 6 6
1 2
1 3
2 3
5 4
6 5
6 4

sample output 2:

6 4 5 4 6 0

#include<stdio.h>
#define N 1010
int map[N][N]={
    0};
int dog[N]={
    0};
int way[N]={
    0};
int n;
int num=0;
void DFS(int x);
int main()
{
    
    int m,s;
    scanf("%d %d %d",&n,&m,&s);
    int i=0;
    int k1,k2;
    for(i=0;i<m;i++){
    
        scanf("%d %d",&k1,&k2);
        map[k1][k2]=1;
        map[k2][k1]=1;
    }
    DFS(s);
    int flag=1;
    for(i=1;i<=n;i++){
    
        if(!dog[i])flag=0;
    }
    for(i=0;i<num;i++){
    
        if(!i)
        printf("%d",way[i]);
        else printf(" %d",way[i]);
    }
    if(!flag) printf(" 0");
}
void DFS(int x)
{
    
    dog[x]++;
    way[num++]=x;
    int i=0;
    for(i=1;i<=n;i++){
    
        if(map[x][i]&&dog[i]==0){
    
            DFS(i);
            way[num++]=x;
        }
    }
}

Finish this problem , I feel that my previous understanding of the diagram is still too superficial , stay BFS and DFS Make some changes in , Will produce some different functions .

void DFS(int x, int pass) {
    
	dog[x] = 1;
	int i = 0;
	now[pass] = x;
	pass++;
	for (i = 0; i < n; i++) {
    
		if (map[x][i] && !dog[i]) {
    
			DFS(i, pass);
		}
	}
	if (pass > maxpass) ntow(pass);// Store the largest virus data in by backtracking way Array 
}

void DFS(int x)
{
    
    dog[x]++;
    way[num++]=x;
    int i=0;
    for(i=1;i<=n;i++){
    
        if(map[x][i]&&dog[i]==0){
    
            DFS(i);
            way[num++]=x;
        }
    }
}

Recursion plus backtracking