文档章节

Codves 2822 爱在心中

Loi_DL
 Loi_DL
发布于 2016/11/03 17:25
字数 368
阅读 5
收藏 0

题面在这自己拿  ↓ 

http://codevs.cn/problem/2822/

找强连通分量,就是找环,用trajian算法dfs记录一下时间戳和能找到的最早的祖先,如果最早的祖先等于当前的时间戳既找到一个环,利用栈维护一下,再开两个数组记录它是在第几个环中并且这个环多大。感谢红太阳lc的help。

#include <iostream>
#include <cstdio>
#include <stack>
using namespace std;
const int maxx=100000;
struct lc 
{
	int f,t;
}es[maxx];
lc bb[maxx];
int tot=0,first[maxx],next[maxx];
void build(int f,int t)
{
	es[++tot]=(lc){f,t};
	next[tot]=first[f];
	first[f]=tot;
}
stack<int> s;
int low[maxx],tim[maxx];
int bh[maxx],siz[maxx];
int tim_clock=0,cnt=0;
void dfs(int x)
{
	tim[x]=low[x]=++tim_clock;
	s.push(x);
	for(int i=first[x];i!=0;i=next[i])
	{
		int v=es[i].t;
		if(tim[v]==0)
		{
			dfs(v);
			low[x]=min(low[x],low[v]);
		}
		if(bh[v]==0)
			low[x]=min(low[x],tim[v]);
	}
	if(low[x]==tim[x])
	{
		cnt++;
		while (1)
		{
			int xx=s.top();
			s.pop();
			siz[cnt]++;
			bh[xx]=cnt;
			if(xx==x)
			break;
		}
	}
}
int cd[maxx];
int main()
{
	int n,m;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d",&bb[i].f,&bb[i].t);
		build(bb[i].f,bb[i].t);
	}
	for(int i=1;i<=n;i++)
		if(tim[i]==0) dfs(i);
	for(int i=1;i<=m;i++)
	{
		int x=bh[bb[i].f],y=bh[bb[i].t];
		if(x!=y) cd[x]++;
	}
	int ans=0,p=0,T=0;
	for(int i=1;i<=cnt;i++)
	{
		if(siz[i]>1)
		{
			T++;
			if(cd[i]==0)
			{
				ans=i;
				p++;
			}
		}
	}
	printf("%d\n",T);
	if(p==1)
	{
		for(int i=1;i<=n;i++)
		if(bh[i]==ans) 
		cout<<i<<" "; 
	}
	else 
	puts("-1");
	return 0;
} 

 

© 著作权归作者所有

Loi_DL
粉丝 0
博文 60
码字总数 48692
作品 0
莱芜
私信 提问
linux命令总结:date

1.功能说明 打印或设置系统日期和时间 2.用法 date [选项] ... [+格式] 日期 [-u | --utc | - universal] [MMDDhhmm [[CC] YY] [。ss]] 3.选项 -d 显示 datestr 中所设定的时间 (非系统时间)...

80后小菜鸟
2017/05/02
0
0
PHP MIME Mail decoder class

PHP MIME Mail decoder class 是一个 PHP 类用来解析 MIME 邮件消息,支持解码单个 RFC 2822 MIME 消息和多个消息归档,支持直接从文件和数据字符串中解析。支持附件解析。...

匿名
2012/03/13
857
0
如何灵活运用Linux 进程资源监控和进程限制

在这篇文章中,我们会介绍一些能够确保系统硬件和软件正常工作的方法,这些方法能够避免潜在的会导致生产环境下线或钱财损失的问题发生。 报告 Linux 进程统计信息 你可以使用 mpstat 单独查...

linuxprobe
2016/10/07
8
0
Gogs v0.9.13 发布,极易搭建的自助 Git 托管服务

Gogs 0.9.13 发布,可选升级。本次提供的 Windows 386 二进制支持 SQLite3 数据库。 Bug 修复 管理员无法在组织首页查看私有仓库 #2372 非本地类型用户允许重置密码 #2811 分支名称包含 ‘#...

无闻
2016/03/20
1K
8
索爱发布 Xperia X8 手机,基于 Android

索爱在全球市场发布新的 Xperia X8 手机,基于 Android 系统,目前尚不清楚具体版本, 该手机主要亮点: 处理器: 600MHz 网络支持: Quad-band GSM/GPRS/EDGE, dual- and tri-band UMTS/HSPA...

红薯
2010/06/17
1K
2

没有更多内容

加载失败,请刷新页面

加载更多

偶遇 JDK 1.8 还未修复的 SecureRandom.getInstance("SHA1PRNG") 之 bug

楼主今天兴高采烈的在部署环境,下载 JDK,打包项目,上传至服务器。 配置 JDK ,打包上传项目楼主就不在这里重复了,读者自行解决哈! 1. 启动项目 java -jar xxxx.jar 令楼主没有想到的是:...

Ryan-瑞恩
18分钟前
7
0
【更新】Stimulsoft Reports v2019.3.1发布,新增对OData v4的支持功能

下载Stimulsoft Report.Ultimate v2019.3.1试用版 集所有报表解决方案于一体的综合性平台 Stimulsoft Reports.Ultimate是集所有报表解决方案于一体的综合性平台,拥有在JavaScript、ASP.NET...

xiaochuachua
18分钟前
1
0
JVM源码分析之javaagent原理完全解读

JVM源码分析之javaagent原理完全解读 概述 本文重点讲述javaagent的具体实现,因为它面向的是我们Java程序员,而且agent都是用Java编写的,不需要太多的C/C++编程基础,不过这篇文章里也会讲...

BryceLoski
24分钟前
1
0
git记住密码

git取消记住密码 git config --system --unset credential.helper git记住密码 git config --global credential.helper store...

大灰狼wow
26分钟前
2
0
java 面试知识点笔记(十四)异常体系

问:Error和Exception的区别? ps:Throwable上层是Object Error:程序无法处理的系统错误,编译器不做检查 Exception:程序可以处理的异常,捕获后可能恢复 RuntimeException:不可预知的,...

断风格男丶
28分钟前
1
0

没有更多内容

加载失败,请刷新页面

加载更多