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