[question 24] logic closed loop (Beijing Institute of Technology / Beijing University of Technology / programming methods and practice / primary school)

Catalog

Description

Ideas

Code  

---

Description

Xiao Zhang is a mystery , He likes watching detective novels and detective movies very much . At the same time, he can also play some reasoning Games , In the detective game , Xiao Zhang needs to explore the connection between events . Through a clue , He can pass events A Infer events B. If through an event A Be able to launch events A In itself , Then he can complete the reasoning . Now in order m Bar clue , Please calculate that he can at least form a logical closed loop with the first few clues to complete the reasoning .

Input first line n,m(1 \leq n,m \leq 300000 ) Two Numbers , Indicates the number of events and clues . Next m That's ok , Two numbers per line A,B(1 \leq A,B \leq n ) , Indicates an event A Be able to launch events B.  

Output Count one line at a time , It means that at least the first few clues can form a logical closed loop to complete reasoning . If the output cannot be completed -1.

Ideas

Still bfs.

In fact, this kind of question is simple bfs, But the details will change a lot .

Like before 22 Non minimum steps occur .

This way 24 Many more details ：

1. The logic closed loop does not need to record the beginning and end , As long as there are numbers in the first few that can form a closed loop
2. Since it is a closed loop , Then any number can be used as the beginning , So you start from A Found B Sure , You can also get it from B Found A
3. How do we determine which one is in the closed loop ？ Is it to create an array to store the first few reads , Then read in each number , For every number in the whole array bfs once ？ Too tired , absolute TLE. You might as well optimize ： Before hypothesis n-1 The number cannot form a closed loop , And with the third n Logarithm forms a closed loop , Note No n Logarithm must be in closed loop , In this way, each time a new number is read in bfs At a time can be .
4. According to this idea , For the first time TLE fall 4 individual hhh, If there is nothing wrong with the algorithm , Or you can't live with the same algorithm if others can  , It must be that you have a lot of miscellaneous steps , Then start to analyze .
5. This question does not require the shortest number of steps , So as long as it can form a logical closed loop , Don't need to use vis Array step , use vis Array requires judgment ,memset, It's a waste of time .
6. Find the specific thinking framework in the code

Code  

TLE fall 4 Version of

#include<cstdio> 
#include<cstring> 
#include<map> 
#include<vector> 
#include<queue> 
#define SIZE 300010 
//int step[SIZE]; 
int cause[SIZE] = { 0 }; 
int result[SIZE] = { 0 }; 
int step; 
std::map<int, std::vector<int>> graph; 
std::queue<int> q; 
bool bfs(int h2, int h1,bool vis[]); 
int main(void) 
{ 
// freopen("input.txt", "r", stdin); 
  int n, m, temp1, temp2; 
    scanf("%d %d", &n, &m); 
    for (step = 1; step <= m; step++) 
   { 
      bool vis[SIZE] = { false }; 
        scanf("%d %d", &temp1, &temp2); 
        graph[temp1].push_back(temp2); 
     if (bfs(temp2, temp1, vis))// Meet the conditions that have appeared before bfs 
        { 
          printf("%d\n", step); 
          return 0; 
      } 
  } 
  // There is no result here  
  printf("-1\n"); 
    return 0; 
} 
bool bfs(int h2,int h1,bool vis[])// From the end bfs To the beginning of the first  
{ 
    int top = h2; 
  q.push(h2); 
    while (!q.empty()) 
 { 
      // Take out  
       top = q.front(); 
       q.pop(); 
       // Put it in the neighbor  
     for (auto x : graph[top]) 
      { 
          if (x == h1) // Find the logic closed loop  
              return true; 
           if (!vis[x]) 
           { 
              q.push(x); 
             vis[x] = true; 
         } 
      } 
  } 
  // Finally empty , Namely bfs Failure  
 return false;                            
}

Remove miscellaneous steps ac edition

#include<cstdio> 
#include<cstring> 
#include<map> 
#include<vector> 
#include<queue> 
#define SIZE 300010 
int step;
std::map<int, std::vector<int>> graph;
std::queue<int> q;
bool bfs(int h2, int h1);
int main(void)
{
    freopen("input.txt", "r", stdin); 
    int n, m, temp1, temp2;
    scanf("%d %d", &n, &m);
    for (step = 1; step <= m; step++)
    {
        scanf("%d %d", &temp1, &temp2);
        graph[temp1].push_back(temp2);
        if (bfs(temp2, temp1))// Meet the conditions that have appeared before bfs 
        {
            printf("%d\n", step);
            return 0;
        }
    }
    // There is no result here  
    printf("-1\n");
    return 0;
}
bool bfs(int h2, int h1)// From the end bfs To the beginning of the first  
{
    int top = h2;
    q.push(h2);
    while (!q.empty())
    {
        // Take out  
        top = q.front();
        q.pop();
        // Put it in the neighbor  
        for (auto x : graph[top])
        {
            if (x == h1) // Find the logic closed loop  
                return true;
            q.push(x);
        }
    }
    // Finally empty , Namely bfs Failure  
    return false;
}