#include iostream#include cstring#include vectorusing namespace std;const int N = 100010;vectorint GN rGN;vectorint S; 存第一次dfs1的结果即标记点的先后顺序优先级小的点先进int visN; visi标记第一次dfs1点i是否访问过int sccnoN; scc

This program is an implementation of the Kosaraju's algorithm to check if a directed graph is strongly connected or not.

The main idea behind the algorithm is to perform two depth-first searches (DFS) on the graph. The first DFS is used to determine the order in which the vertices should be processed in the second DFS. The second DFS is used to find the strongly connected components (SCCs) of the graph.

The program first defines a constant N to represent the maximum number of vertices in the graph. It also includes the necessary header files and declares the required variables and data structures.

The dfs1() function is used to perform the first DFS. It takes a vertex u as input and marks it as visited. Then, it recursively calls dfs1() on all the adjacent vertices of u. Finally, it adds the vertex u to the S vector, which keeps track of the order in which the vertices are visited.

The dfs2() function is used to perform the second DFS. It takes a vertex u as input and marks it as belonging to the current SCC. Then, it recursively calls dfs2() on all the vertices that can be reached from u in the reverse graph.

The Kosaraju() function is the main function that implements the Kosaraju's algorithm. It initializes the variables and data structures, and then calls dfs1() for each vertex in the graph. After that, it reverses the graph and calls dfs2() for each vertex in the reverse graph. Finally, it checks the number of SCCs found and prints "Yes" if there is only one SCC, and "No" otherwise.

The main() function reads the number of vertices and edges from the input and constructs the graph accordingly. It then calls the Kosaraju() function and prints the result.

The program continues to read input until both n and m are zero.

Overall, this program efficiently checks whether a directed graph is strongly connected or not using the Kosaraju's algorithm