上白泽慧音

题目链接

强联通分量模板题,Tarjan求强联通分量,记录大小即可

#include<iostream>
#include<cstring>
#include<cstdio>
#define N 5010
#define M 100010
int n,m,Head[N],Enum,stack[N],top,ms;
int dfn[N],cnt,low[N],belong[N],size[N],num;
bool ins[N];
struct NODE{
int to,next;
} e[M];
inline void add(int x,int y){
e[++Enum].to=y;
e[Enum].next=Head[x];
Head[x]=Enum;
}
inline int read(){
int x=; char c=getchar();
while(c<''||c>'') c=getchar();
while(''<=c&&c<='') { x=(x<<)+(x<<)+c-''; c=getchar(); }
return x;
}
inline void Tarjan(int u){
dfn[u]=low[u]=++cnt;
ins[u]=; stack[++top]=u;
for(int i=Head[u];i;i=e[i].next){
int v=e[i].to;
if(!dfn[v]){
Tarjan(v);
low[u]=std::min(low[u],low[v]);
}
else if(ins[v])
low[u]=std::min(low[u],dfn[v]);
}
if(low[u]==dfn[u]){
belong[u]=++num;
while(stack[top]!=u){
int k=stack[top];
belong[k]=num;
size[num]++;
ins[k]=;
top--;
} size[num]++;
top--; ins[u]=;
}
}
int main()
{
n=read(); m=read();
int x,y,t;
for(int i=;i<=m;i++){
x=read(); y=read(); t=read();
add(x,y); if(t==) add(y,x);
}
for(int i=;i<=n;i++)
if(!dfn[i]) Tarjan(i);
for(int i=;i<=num;i++)
if(size[i]>ms) ms=size[i];
int ans;
for(int i=;i<=n;i++)
if(size[belong[i]]==ms){
ans=belong[i];
break;
}
printf("%d\n",ms);
for(int i=;i<=n;i++)
if(belong[i]==ans)
printf("%d ",i);
puts("");
return ;
}

最新文章

  1. 前端Javascript书籍分享
  2. Alpha版本十天冲刺——Day 8
  3. 模拟赛1031d2
  4. Leetcode: Pacific Atlantic Water Flow
  5. 关于android软键盘enter键的替换与事件监听
  6. 函数执行到return就结束了
  7. nyoj10 滑雪
  8. linux vim 个性化设置(.vimrc)
  9. 前端技术API手册(2) -- CSS API 的实现
  10. 二叉树Bynary_Tree(2):二叉树的递归遍历
  11. 抓包工具Fidder详解
  12. 利用tornado实现表格文件预览
  13. python 爬虫与数据可视化--爬虫基础知识
  14. [转]ps命令详解
  15. 数据库之sql语句汇总20180616
  16. yii2 modules模块配置指南
  17. 咏南中间件支持DELPHI6及以上版本开发的客户端
  18. (转)Groupon前传:从10个月的失败作品修改,1个月找到成功 并不挶泥在这个点子上面,它反而往后站一步,看看他们已经做好的这个网站,可以再怎么包装成另一个完完全全不同的网站?所有的人所做的每件失败的事情中, 一定有碰到或含有成功的答案」在里面,只是他们不知道而已。 人不怕失败」,只怕宣布失败」
  19. &lt;NET CLR via c# 第4版&gt;笔记 第13章 接口
  20. static 和 global

热门文章

  1. 测试次数(C++)
  2. vim配置clojure开发环境备忘录
  3. SpringBoot - 工程搭建
  4. java selector
  5. struts2====之=======初识struts
  6. node-sass安装失败的解决办法
  7. 前端之CSS——盒子模型和浮动
  8. 使用angular帮你实现拖拽
  9. wx.grid 简单例子
  10. 仿照jQuery写一个关于选择器的框架(带了注释,请多多指教~)