Study diary: February 13, 2022

Today's first question

If we have such a set of data

9 11
7 8
8 9
9 7
4 1
7 3
1 2
2 5
5 6
6 2
1 3
3 4

For better comparison , We also draw the corresponding diagram

It's almost like this

From the picture, we can directly see ,1-2 and 3-7

Other roads that do not meet the conditions basically have a common feature , It can be connected with other roads to form a closed loop

So we can eliminate the routes on all closed rings , The remaining route is the final result

In order to meet the output required by the topic , We must sort .

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

Suppose we start from the city 1 Start walking , The way to go is the depth first algorithm

from 1 Go down 1-2 Go to the 2

Judge the city 2 Whether it's the city you've passed , No, just keep going

from 2 Go down 2-5 Go to the 5

Judge the city 5 Whether it's the city you've passed , No , Keep going down

from 5 Go down 5-6, Go to the 6

Judge the city 6 Whether it's the city you've passed , No , Keep going down

from 6 Go down 6-2, Go to the 2

Judge the city 2 Whether it's the city you've passed , yes . It shows that a ring is formed in front , Look ahead , The starting point is 2 The route of the , And mark all routes along the way

So it includes itself , And along the way 2-6,5-6,2-5 All marked

So from 1-2 All the above routes have been traversed

And then from 1-3 The route starts

Judge the city 3, Keep going down -7

Judge the city 7, Keep going down -8

Judge the city 8, Keep going down -9

Judge the city 9, Keep going down -7

Judge the city 7, It's past , Mark the route along the way 7-9,8-9,7-8

We continue from the city 3 go , Go down -4

Judge the city 4, Keep going down -1

Judge the city 1, It's past , Mark the route along the way 1-3,3-4,1-4

All routes have been judged , The final output is an unmarked route

1-2 and 3-7 

Among them, several tags are needed

A mark of the route taken ,

A sign of the city passed

A route marked as a ring

The final code is as follows

#include<iostream>
using namespace std;
struct Data
{
    int a;
    int b;
}data[5003];
int don[5003]={0};// Mark the route taken 
int result[5003]={0};// Record the final result 
int steep[200];// Record the cities you have passed 
int n,m;
int run(int start,int end)
{
    int mid=(start+end)/2;
    int a=start;
    int b=mid+1;
    Data shadow[5003];
    int len=0;
    while(a<=mid&&b<=end)
    {
        if(data[a].a<data[b].a)
        {
            shadow[len++]=data[a++];
        }
        else
        if(data[a].a==data[b].a)
        {
            if(data[a].b<data[b].b)
            shadow[len++]=data[a++];
            else
            shadow[len++]=data[b++];
        }
        else
        shadow[len++]=data[b++];
    }
    while(a<=mid)
    shadow[len++]=data[a++];
    while(b<=end)
    shadow[len++]=data[b++];
    for(int i=0;i<len;i++)
    data[start+i]=shadow[i];
}
int sorting(int start,int end)
{
    if(start>=end)
    return 0;
    int mid=(start+end)/2;
    sorting(start,mid);
    sorting(mid+1,end);
    run(start,end);
}



// Mark the route along the way 
int clear(int present,int goal,int flag)
{
    result[present]=1;
    if(flag==0)
    if(data[present].a==goal||data[present].b==goal)
    return 0;
    present=don[present];
    clear(present,goal,0);
}
int finding(int present,int cit)
{
    if(steep[cit])
    {
        clear(present,cit,1);
        return 0;
    }
    for(int i=1;i<=m;i++)
    {
        if(don[i]==0)
        {
            if(data[i].a==cit)
            {
                don[i]=present;// Mark the route taken , Record the last step 
                steep[data[i].a]=1;// Mark the city you have passed 
                finding(i,data[i].b);// Go to the next city 
            }
            if(data[i].b==cit)
            {
                don[i]=present;// Mark the route taken , Record the last step 
                steep[data[i].b]=1;// Mark the city you have passed 
                finding(i,data[i].a);// Go to the next city                 
            }
        }
    }
}
int main()
{
    cin>>n>>m;
    int a,b;
    for(int i=1;i<=m;i++)
    {
        cin>>a>>b;
        // When deposited a Must be less than b
        if(a>b)
        data[i].a=b,data[i].b=a;
        else
        data[i].a=a,data[i].b=b;
    }
    sorting(1,m);// Sort 
    finding(1,data[1].a);
    for(int i=1;i<=m;i++)
    {
        if(result[i]==0)
        cout<<data[i].a<<' '<<data[i].b<<endl;
    }
}

To sum up, this problem is called joint search , A set of depth first algorithms .

Mainly depth first algorithm

Execute special orders according to the special conditions explored , To arrive at the final result