洛谷P1726

题目简述

在一个有向图中，寻找最大的连通分量并输出(如果有两个连通分量相同输出字典序小的)。

相关知识

连通
无向图中的两个点可相互到达，则这两个点是连通的。
有向图中的两个点可相互到达，则这两个点是强连通的。

连通图
无(有)向图中，所有的点都可相互到达。

连通分量
无向图中的连通分量是个子图，该子图中任意两个点可互相到达。
有向图中称为强连通分量，强连通分量是个子图，该子图中任意两个点可互相到达。

时间戳
在一次搜索过程中，第几个搜索到这个点，这个点的时间戳就为几。

相关变量

每个点有两个参数，dfn，low。
dfn表示该点的时间戳，low表示该点可以到达的所有点中最小的时间戳。

思路

在dfs的过程中不断更新dfn,low这两个变量，并将访问到的点入栈。
具体操作：每到达一个点，先将该点入栈，然后尝试访问下一个点，
若下一个点没有被访问过，则dfs，
若下一个点被访问过且在当前栈里，则直接利用下一个点的dfn更新当前点的low。
dfs回溯的过程中也要更新low。

我们先看下在一个连通图中使用该算法是个什么情况。

我们从1开始，先将1入栈，此时1号点的dfn，low都为1，其它点为初始值0。

从1号点来到2号点，将2入栈并更新dfs与low。

从2来到3进行相同的操作。

从3试图访问1就要注意了，由于1已经在栈里，故不对1dfs，直接更新3的low，然后开始回溯。

从3回到2时，用3的low更新2的low(即low[2]=min(low[2],low[3]))，这是因为3能到达的点2一定能到达。

最后回到1，从1开始的dfs结束，此时有\(low[1]==dfn[1]\)，这意味着我们找到了一个连通分量1,2,3。
此时\(low[2]==low[3]==1\)。这说明2，3都能到达1，又因为这次dfs是从1开始，所以1也能到达2，3。
这就解释了为什么这些变量(dfn,low)能确定一个连通分量。
再看栈中的元素，2，3都位于1的上面，将1及以上的元素出栈即可得到对应的连通分量。
具体细节请看代码

参考代码

#include
using namespace std;
const int N=5e3+10;
vectorg[N];//存图
int n,m;
int ans,f[N],cnt[N],Max;
//ans是连通分量的个数，f[i]表示i属于哪个连通分量，cnt[i]表示第i个连通分量的大小
//Max是最大连通分量的大小
int dfn[N],low[N],tim;
stackst;//栈来存储连通分量
void targan(int x){
    st.push(x);//每到一个元素先入栈
    dfn[x]=low[x]=++tim;//更新dfn与low
    for(int i=0;i