tarjan

tarjan缩点的运用,寻找一个较小的点集使得从这些点出发能够到达任意不在点集中的点,若有多个点,输出这些集合升序排序后字典序最小的

可达性
思路:先进行缩点,再寻找出入度为0的强连通分量
du数组记录的是每个强连通分量的入度
cnt数组记录的是每个强连通分量中的最小点
sig记录的是强连通分量的个数

#include<bits/stdc++.h>
#define M 100100
using namespace std;
int low[M],dfn[M],tot,sig,temp;
stack<int> s;
int col[M],dep[M],n,m;
int du[M],cnt[M];
int ans[M],vis[M];
vector<int>vep[M];
void init( )
{
      tot=sig=temp=0;
      memset(vis,0,sizeof(vis));
      memset(low,0,sizeof(low));
      memset(col,0,sizeof(col));
      memset(dfn,0,sizeof(dfn));
      memset(dep,0,sizeof(dep));
      memset(du,0,sizeof(du));
      memset(cnt,M,sizeof(cnt));
      memset(ans,0,sizeof(ans));
      for(int i=0;i<M;i++)
      {
            vep[i].clear( );
      }
}
void tarjan(int x)
{
      dfn[x]=low[x]=++tot;
      s.push(x);
      vis[x]=1;
      for(int i=0;i<vep[x].size( );i++)
      {
            int j=vep[x][i];
            if(!dfn[j])
            {
                  tarjan(j);
                  low[x]=min(low[x],low[j]);
            }
            else if(vis[j])
            {
                  low[x]=min(low[x],dfn[j]);
            }
      }
      if(low[x]==dfn[x])
      {
            sig++;
            int k;
            do
            {
                  k=s.top( );
                  col[k]=sig;
                  vis[k]=0;
                  s.pop( );
            }while(x!=k);
      }
      return ;
}
void solve(int n)
{
      for(int i=1;i<=n;i++)
      {
            if(!dfn[i])
            {
                  tarjan(i);
            }
      }
      for(int i=1;i<=n;i++)
      {
            cnt[col[i]]=min(cnt[col[i]],i);
            for(int j=0;j<vep[i].size( );j++)
            {
                  int v=vep[i][j];
                  if(col[v]!=col[i])
                  {
                        du[col[v]]++;
                  }
            }
      }
      for(int i=1;i<=sig;i++)
      {
            if(du[i]==0)
            {
                  temp++;
                  ans[temp]=cnt[i];
            }
      }
      cout<<temp<<endl;
      sort(ans+1,ans+1+temp);
      for(int i=1;i<=temp;i++)
      {
            cout<<ans[i]<<" ";
      }
      cout<<endl;
      return ;
}
int main( )
{
      int x,y;
      cin>>n>>m;
      init();
      for(int i=1;i<=m;i++)
      {
            cin>>x>>y;
            vep[x].push_back(y);
      }
      solve(n);
      return 0;
}
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 216,402评论 6 499
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 92,377评论 3 392
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 162,483评论 0 353
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 58,165评论 1 292
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 67,176评论 6 388
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 51,146评论 1 297
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 40,032评论 3 417
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 38,896评论 0 274
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 45,311评论 1 310
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 37,536评论 2 332
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 39,696评论 1 348
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 35,413评论 5 343
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 41,008评论 3 325
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 31,659评论 0 22
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 32,815评论 1 269
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 47,698评论 2 368
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 44,592评论 2 353

推荐阅读更多精彩内容

  • 无向图中求割点集和割边集——Tarjan算法割点和割边定义在一个无向图中,如果删除了某个顶点及与之相连的所有边,产...
    Herixth阅读 13,099评论 3 8
  • 在最近学习中遇到了几次题解使用Tarjan的情况,便查了一些资料。 算法简介 一种由Robert Tarjan提出...
    vfence阅读 1,599评论 0 1
  • 概念 强联通:如果有向图中两个点vi和vj,其中vi到vj之间有一条有向路径,vj到vi有一条有向路径,则称vi,...
    idella阅读 872评论 0 0
  • tarjan寻找出度为0的强连通分量,从小到大输出此强连通分量中的点 poj 2553 The Bottom of...
    雨落八千里阅读 165评论 0 1
  • tarjan:寻找出度为0的强连通分量,并求出该强连通分量中有多少个点。 sig表示的是强连通分量的个数其中col...
    雨落八千里阅读 113评论 0 1