\documentclass[UTF8]{ctexart}
\usepackage[ruled, linesnumbered]{algorithm2e}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{boxedminipage}
\usepackage{circuitikz}
\usepackage{fancyhdr}
\usepackage{float}
\usepackage{fullpage}
\usepackage{gensymb}
\usepackage{geometry}
\usepackage{graphicx}
\usepackage{hyperref}
\usepackage{interval}
\usepackage{listings}
\usepackage{mflogo}
\usepackage{multirow}
\newcommand{\nop}[1]{}
\usepackage{siunitx}
\usepackage{subfigure}
\usepackage{texnames}
\usepackage{textcomp}
\usepackage{tikz}
\usepackage{titlesec}
\usepackage{wrapfig}
\usepackage{xcolor}
\usepackage{xltxtra}

\geometry{left=2.5cm,right=2.5cm,headsep=1cm,bottom=2cm,footnotesep=2cm,headheight=13pt}
\pagestyle{fancy}
\fancyfoot[C]{\thepage}
\fancyhead[L]{计算机科学与技术系}
\fancyhead[C]{\ \ \ \ \ \ \ \ }
\fancyhead[R]{\ \ \ \ \ \ \ \ \ \ \ \ 2023年4月21日}

\ctexset{
    section={
        format+ = \Large \raggedright,
    }
}

\newtheorem{theorem}{定理}
\newtheorem{lemma}{引理}
\newtheorem{definition}{定义}

\parindent0mm
%\pagestyle{empty}

\usetikzlibrary{automata, positioning, arrows}

\newcounter{aufgc}
\newenvironment{example}[1]%
{\refstepcounter{aufgc}\textbf{例题1.\arabic{aufgc}} \emph{#1} \\}
{\vspace{0.2cm}}%

\renewcommand{\labelenumi}{(\alph{enumi})}

\lstset{basicstyle=\ttfamily}

\begin{document}

\section*{图}

$G=(V,E)$，$n$个点，$m$条边

邻接矩阵，邻接表

深度优先搜索

(强)连通分量

在有向图中用线性时间找到强连通分量，时间戳

\begin{algorithm}
    \caption{深度优先搜索}
    \SetKwFunction{DE}{DFS-Explore}
    \SetKwFunction{DFS}{DFS}
    \SetKwProg{Fn}{Function}{:}{end\ Function}
    \Fn{\DE{$u$}}{
        $t=t+1$\\
        $u.d=t$\\
        $visited[u]=True$\\
        \ForEach{$v\in Adj[u]$}{
            \If{$visited[v]=False$}{
                $v.p=u$\\
                \DE{$v$}
            }
        }
        $t=t+1$
        $u.f=t$
    }
    \Fn{\DFS{$G$}}{
        $t=0$\\
        \ForEach{$u\in V$}{
            $visited[u]=False$\\
            $u.p=Nil$
        }
        \ForEach{$u\in V$}{
            \If{$visited[u]=False$}{
                \DE{$u$}
            }
        }
    }
\end{algorithm}

\section*{找强连通分量}

源source/汇sink强连通分量

如果一个DFS从汇强连通分量开始，那么这个DFS会正确找到整个强连通分量，
但如果从源强连通分量开始，则会经过多个强连通分量

所以，需要找到一个汇强连通分量。

经过一次DFS之后，结束时间戳最大的点一定在源强连通分量上。

同时考虑反向图，此时得到的源强连通分量即为原图的汇强连通分量。
在算法中，反向图表示为邻接矩阵的转置$A^{\top}$.

总体执行如下：先调用之前的DFS算法，然后对$G^{\top}$调用DFS，在外层循环
中按$u.f$递减顺序进行DFS，这样每棵搜索树均对应一个强联通分量.

\end{document}
