当前位置:网站首页>Deep search + backtracking
Deep search + backtracking
2022-06-11 05:03:00 【bolite】
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 { a1 ,⋯,an } Ratio sequence { b1 ,⋯,bn } “ Small ”, If there is 1≤k≤n Satisfy ai =bi For all i<k establish , And ak <bk .
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
边栏推荐
- 博途仿真时出现“没有针对此地址组态任何硬件,无法进行修改”解决办法
- New product pre-sale: 25g optical network card based on Intel 800 series is coming
- Exhibit express: Lianrui will bring three new products of the industry to debut in visionchina (Shenzhen) 2021
- C language test question 3 (program multiple choice question - including detailed explanation of knowledge points)
- White Gaussian noise (WGN)
- 力扣(LeetCode)161. 相隔为 1 的编辑距离(2022.06.10)
- [Transformer]MViTv2:Improved Multiscale Vision Transformers for Classification and Detection
- Technology | image motion drive interpretation of first order motion model
- 华为设备配置BGP/MPLS IP 虚拟专用网
- Dongmingzhu said that "Gree mobile phones are no worse than apple". Where is the confidence?
猜你喜欢

Huawei equipment is configured to access the virtual private network through GRE tunnel

Huawei equipment is configured to access the virtual private network through GRE

Simple knowledge distillation

The solution "no hardware is configured for this address and cannot be modified" appears during botu simulation

华为设备配置BGP/MPLS IP 虚拟专用网地址空间重叠

Huawei equipment is configured with bgp/mpls IP virtual private network

Vins fusion GPS fusion part

Iris dataset - Introduction to machine learning

codesys 獲取系統時間

Tightly coupled laser vision inertial navigation slam system: paper notes_ S2D. 66_ ICRA_ 2021_ LVI-SAM
随机推荐
Carrier coordinate system inertial coordinate system world coordinate system
[NIPS2021]MLP-Mixer: An all-MLP Architecture for Vision
Reverse thinking: making cartoon photos real
新库上线 | CnOpenData不可移动文物数据
Possible errors during alphapose installation test
What is the difference between gigabit network card and 10 Gigabit network card?
Target detection - personal understanding of RCNN series
华为设备配置MCE
Huawei equipment is configured to access the virtual private network through GRE
Network security construction in 5g Era
Following the wave of lack of core, Lianrui launched a number of gigabit network card solutions
How to choose a suitable optical network card?
Paper reproduction: pare
Deep extension technology: intelligent OCR recognition technology based on deep learning has great potential
go单元测试实例;文件读写;序列化
Visual (Single) Object Tracking -- SiamRPN
[Transformer]MViTv1:Multiscale Vision Transformers
Using keras to build the basic model yingtailing flower
Technology | image motion drive interpretation of first order motion model
Leetcode question brushing series - mode 2 (datastructure linked list) - 19:remove nth node from end of list (medium) delete the penultimate node in the linked list