还有人用tarjan缩点?

还有人用tarjan缩点?

#include <stdio.h>
#include <string.h>
#define N 100005
int n,m,i,j,k,a,b,ans;
int f[N],v[N],h[N],c[N];
struct AB{
   int a,b,n;
}d[N*3];
void charu(int a,int b){//建立a到b的有向边
    d[++k].a = a,d[k].b = b;
    d[k].n = h[a],h[a] = k;
}
int find(int x){//并查集找函数
   if(x == f[x])rerturn x;
   return f[x] = find(f[x]);
}
void dfs(int a){//dfs+并查集求强连通分量
   int b,i;
   for(i=h[a];i;i=d[i].n){
     b = d[i].b;//当前点是a下一个点是b
     if(!v[b]){//没访问过
         v[b] = v[a] + 1;//用深度记录访问过
         dfs(b);//搜索他 访问他
     }
     if(v[find(b)]>0){//b所在强连通子图访问中
        if(v[find(a)]<v[f[b]]) f[f[b]] = f[a];
        else f[f[a]] f[b];
     }//合并a和b两子强连通子图,并选择深度小的做祖先
   }
   v[a] = -1;//深度为负数表示访问完
}
void dp(int a){//dp求路径长度 最长路
   int b,i,j=0;
   v[a] = 0;//访问过 下次不再访问
   for(i=h[a];i;i=d[i].n){
      b = d[i].b;//下一个点
      if(v[b]) dp(b);
      if(c[b] > c[j])j = b;//记录最大值编号
  }
  c[a] += c[j];//选最多景点那条路
}
int main()
   scanf("%d%d",&a,&b);
   for(i=1;i<=n;i++) f[i] = i;//并查集赋初值
   for(i=1;i<=n;i++){//求强连通分量
     if(!v[i]){
         v[i] = 1;
         dfs(i);
    }
  }//统计强连通分量中点的个数 记录到祖先结点  
  for(i=1;i<=n;i++) c[find(i)]++;
  memset(h,0,sizeof(h));
  for(k=0,i=1;i<=m;i++){//重新建边
     a=f[d[i].a],b = f[d[i].b];
  }
  for(i=1;i<=n;i++){//求出每个点出发的最多景点数
     if(i == f[i]&&v[i])
     if(c[i]>ans)ans = c[i];//记录最大值
  }
  printf("%d\n",ans);//输出结果
  return 0;
}

 

 

© 版权声明
THE END
喜欢就支持一下吧
点赞15 分享
评论 抢沙发
头像
欢迎您留下宝贵的见解!
提交
头像

昵称

取消
昵称表情代码图片快捷回复

    暂无评论内容