Wannafly挑战赛14 C.可达性(tarjan缩点)
2024-09-12 11:15:12
题目描述
给出一个 0 ≤ N ≤ 105 点数、0 ≤ M ≤ 105 边数的有向图,
输出一个尽可能小的点集,使得从这些点出发能够到达任意一点,如果有多个这样的集合,输出这些集合升序排序后字典序最小的。
输出一个尽可能小的点集,使得从这些点出发能够到达任意一点,如果有多个这样的集合,输出这些集合升序排序后字典序最小的。
输入描述:
第一行为两个整数 1 ≤ n, m ≤ 105,接下来 M 行,每行两个整数 1 ≤ u, v ≤ 105表示从点 u 至点 v 有一条有向边。数据保证没有重边、自环。
输出描述:
第一行输出一个整数 z,表示作为答案的点集的大小;
第二行输出 z 个整数,升序排序,表示作为答案的点集。
示例1
输入
7 10
4 5
5 1
2 5
6 5
7 2
4 2
1 2
5 3
3 5
3 6
输出
2
4 7
题意
如上
题解
求有向图的最大强连通加上缩点,输出缩完后每个强连通子集的最小的点即可
强连通分量:有向图强连通分量:在有向图G中,如果两个顶点vi,vj间(vi>vj)有一条从vi到vj的有向路径,同时还有一条从vj到vi的有向路径,则称两个顶点强连通。如果有向图G的每两个顶点都强连通,称G是一个强连通图。有向图的极大强连通子图,称为强连通分量
缩点:因为强连通分量中的每两个点都是强连通的,可以将一个强连通分量当做一个超级点
代码
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+;
vector<int>G[N],id[N]; int low[N],dfn[N],instack[N],st[N],tot,cnt,scc,p;
int belong[N],in[N];
void tarjan(int u)
{
int v;
low[u]=dfn[u]=++tot;//时间戳
st[++cnt]=u;//入栈
instack[u]=;
for(int i=;i<G[u].size();i++)
{
v=G[u][i];
if(!dfn[v])//是否已经访问
{
tarjan(v);
low[u]=min(low[u],low[v]);
}
else if(instack[v])//已经访问过并且在栈里
{
low[u]=min(low[u],dfn[v]);
}
}
if(low[u]==dfn[u])
{
scc++;//强连通
do{
v=st[cnt--];//出栈
instack[v]=;//v出栈后
belong[v]=scc;//v属于哪个强连通1-scc
id[scc].push_back(v);//当前强连通的子集
}while(u!=v);
}
}
int main()
{
int n,m,u[N],v[N];
scanf("%d%d",&n,&m);
for(int i=;i<=m;i++)
{
scanf("%d%d",&u[i],&v[i]);
G[u[i]].push_back(v[i]);
}
for(int i=;i<=n;i++)//求所有强连通
if(!dfn[i])//是否已经访问过
tarjan(i);
for(int i=;i<=m;i++)//缩点
{
if(belong[u[i]]==belong[v[i]])continue;
in[belong[v[i]]]++;
}
for(int i=;i<=scc;i++)
sort(id[i].begin(),id[i].end());
vector<int> res;
for(int i=;i<=scc;i++)
if(!in[i])
res.push_back(id[i][]);
printf("%d\n%d",res.size(),res[]);
for(int i=;i<res.size();i++)
printf(" %d",res[i]);
return ;
}
最新文章
- angularjs $broadcast $emit $on 事件触发controller间的值传递
- jsp和mysql乱码
- zabbix微信告警(虚拟机脚本测试成功,zabbix上收不到信息)
- bzoj2631: tree
- 学习之路三十九:新手学习 - Windows API
- cocos2dx win打包apk
- nginx指令
- MYSQL基础01(新增,修改,删除)
- Java API —— Set接口 &; HashSet类 &; LinkedHashSet类
- VMWare Workstation 占用443端口导致apache启动不了
- Quartz2D使用
- C# 使用 Code Snippet 简化 Coding
- Dynamics CRM JS的调试的弊端解决办法
- c语言-转义序列
- 安装Eclipse(android)新建项目时遇到的问题
- 推荐vim学习教程--《Vim 练级手册》
- 洛谷P4117 [Ynoi2018]五彩斑斓的世界 [分块,并查集]
- VB6 变量定义作用域的一个奇特形式
- 理解 Redis(6) - List 值
- sublime 打开import require 模块文件的url 或路径的插件