[Tarjan/最大连通分量] P1726 上白泽慧音
[Tarjan/最大连通分量] P1726 上白泽慧音
[Tarjan/最大连通分量] P1726 上白泽慧音
于2022年6月10日2022年6月10日由Sukuna发布
在幻想乡，上白泽慧音是以知识渊博闻名的老师。春雪异变导致人间之里的很多道路都被大雪堵塞，使有的学生不能顺利地到达慧音所在的村庄。因此慧音决定换一个能够聚集最多人数的村庄作为新的教学地点。人间之里由N个村庄（编号为1..N）和M条道路组成，道路分为两种一种为单向通行的，一种为双向通行的，分别用1和2来标记。如果存在由村庄A到达村庄B的通路，那么我们认为可以从村庄A到达村庄B，记为(A,B)。当(A,B)和(B,A)同时满足时，我们认为A,B是绝对连通的，记为<A,B>。绝对连通区域是指一个村庄的集合，在这个集合中任意两个村庄X,Y都满足<X,Y>。现在你的任务是，找出最大的绝对连通区域，并将这个绝对连通区域的村庄按编号依次输出。若存在两个最大的，输出字典序最小的，比如当存在1,3,4和2,5,6这两个最大连通区域时，输出的是1,3,4。
输入格式
第1行：两个正整数N,M
第2..M+1行：每行三个正整数a,b,t, t = 1表示存在从村庄a到b的单向道路，t = 2表示村庄a,b之间存在双向通行的道路。保证每条道路只出现一次。
输出格式
第1行： 1个整数，表示最大的绝对连通区域包含的村庄个数。
第2行：若干个整数，依次输出最大的绝对连通区域所包含的村庄编号。
下面给定定义时间戳：搜索到一个点时，这个点将被赋予一个 唯一 的时间量，并且越早搜到的点时间戳越小（当然了）.我们需要寻找的就是在DFS搜索生成的搜索树、图-树=被抛弃的边.对于被抛弃的边,我们需要找到后向边,这种边容易构成回路.那怎么找后向边呢?就需要我们的时间戳了.
Tarjan算法使用两个数组来维护这个信息：
- dfn[maxn]:储存每个点的时间戳
- low[maxn]:储存每个点访问祖先的能力
什么是访问祖先的能力呢？就是说，这个点最多能走回头路到什么地步，low数组储存的是他能访问到的最早祖先的dfn值，如果这个点没有回头路可走，那low值就是他自己的dfn值咯.
struct edge{
int x,y,w;
}E[maxm];
int dfn[maxn],low[maxn],tmmk=0;
int head[maxn]//链式前向星,获取邻接的点.
int next[maxn]//模拟链表,来获得数据
bool v[maxn];//v数组用来跟踪这个点是否已经处理完毕，我们稍后会见到它的用法
stack<int> S;
void tarjan(int x)
{
dfn[x]=low[x]=++tmmk;//每个点在最开始被访问时，时间戳和low值都是一样的
S.push(x);
v[x]=true;
for(int i=head[x];i;i=next[i])//链式前向星查邻接点
{
int y=E[i].y;//不熟悉的同学请像这样打多一点，有助于理解
if(!dfn[y])//dfn的初值都是0，如果这个点没有搜过，就递归搜索
{
tarjan(y);
low[x]=min(low[x],low[y]);//此时搜索已经回溯，我们可以确定y的low值已经更正，所以用它来更新x的
}//因为y在x的后面，所以y能访问到的祖先x一定可以访问到
else
if(v[y])//如果y点搜过了且在栈里，说明我们找到了 后！向！边！
low[x]=min(low[x],dfn[y]);
}//但是此时我们还不能急着处理，为什么？因为有回溯到根了以后我们在收集到了完整的信息
if(dfn[x]==low[x])
{//dfn和low一样，你就是与众不同的根节点
ans++;//ans是强连通分量的个数
int y;
do{
y=S.top();
S.pop();
v[y]=false;
col[y]=ans;//y点属于编号为ans的强连通分量
g[ans].push_back(y);//存下每个强连通分量的成员
}while(y!=x)//在这里将栈里的点全部倒出来（倒垃圾一样..）
}
}