在幻想乡,上白泽慧音是以知识渊博闻名的老师。春雪异变导致人间之里的很多道路都被大雪堵塞,使有的学生不能顺利地到达慧音所在的村庄。因此慧音决定换一个能够聚集最多人数的村庄作为新的教学地点。人间之里由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)//在这里将栈里的点全部倒出来(倒垃圾一样..) 
   }
}
分类: 测试

0 条评论

发表评论

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用*标注

隐藏