poj1236(强连通分量)-程序员宅基地

技术标签: dfs  算法  强连通分量  

题意:
(1).至少需要向多少个学校发放软件,要使这个网络中的所有学校都能得到软件
(2).至少需要添加多少条边,才能使这个网络成为一个强连通分量图。
思路:首先求解强连通分量,如果不是同一个强连通分量,则将入度indegree[blong[v]]++outdegree[blong[i]]++。在这些强连通分量中如果入度为零,则需要发放ans1个软件,问题的求解。问题2的求解是求这个max(ans1,ans2).

强连通图:在有向图中,任意节点除法都可以到达其余所有节点,则称为强连通图。
强连通分量:在非强连通图的有向图中,选取部分点为强连通图,该强连通子图称为强连通分量。
求出强连通分量可以进行缩点操作。
一个强连通图的出度和入度是相同的:首先我们先用tarjan缩点,把一些强连通集合变成一个新的点,然后找出新的点的出度和入度,输出最大就行了。

#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<vector>
#include<stack>
using namespace std;
const int maxx=20005;
const int inf=0x3f3f3f3f;
int low[maxx];
int dfn[maxx];
int vis[maxx];
int flag[maxx];
int blong[maxx];//记录这个节点属于哪个强连通分量 
int indegree[maxx];//记录入度 
int outdegree[maxx];//记录出度 
int index;
int tcost[maxx];
int root;
int ans;//记录强连通分量的个数 
int n,m;
stack<int>s;
vector<int>G[maxx];
void dfs(int u){
    
	index++;
	low[u]=dfn[u]=index;
	s.push(u);
	vis[u]=1;
	for(int i=0;i<G[u].size();i++){
    
		int v=G[u][i];
		if(dfn[v]==0){
    
			dfs(v);
			low[u]=min(low[u],low[v]);
		}else if(vis[v]==1){
    
			low[u]=min(low[u],dfn[v]);
		}
	}
	if(dfn[u]==low[u]){
    
		ans++;
		int v;
		do{
    
			v=s.top();
			s.pop();
			blong[v]=ans;
			vis[v]=0;
		}while(u!=v);
	}
}
void init(){
    
	ans=0;
	memset(flag,0,sizeof(flag));
	memset(vis,0,sizeof(vis));
	memset(low,0,sizeof(low));
	memset(dfn,0,sizeof(dfn));
	memset(blong,0,sizeof(blong));
	memset(indegree,0,sizeof(indegree));
	memset(outdegree,0,sizeof(outdegree));
	while(!s.empty())s.pop();
	for(int i=0;i<=n;i++){
    
		G[i].clear();
	}
}
int main(){
    
	while(scanf("%d",&n)!=EOF){
    
		init();
		for(int i=1;i<=n;i++){
    
			int t;
			while(scanf("%d",&t)){
    
				if(t==0){
    
					break;
				}
				G[i].push_back(t);
			}
		}
		ans=0;
		index=1;
		for(int i=1;i<=n;i++){
    
			if(dfn[i]==0){
    
				dfs(i);
			}
		}
		for(int i=1;i<=n;i++){
    
			for(int j=0;j<G[i].size();j++){
    
				int v=G[i][j];
				if(blong[i]!=blong[v]){
    
					outdegree[blong[i]]++;
					indegree[blong[v]]++;
				}
			}
		}
		int ans1=0,ans2=0;
		if(ans==1){
    
			cout<<1<<endl;
			cout<<0<<endl;
		}else {
    
			for(int i=1;i<=ans;i++){
    
				if(indegree[i]==0){
    
					ans1++;
				}
				if(outdegree[i]==0){
    
					ans2++;
				}
			}
			cout<<ans1<<endl;
			int tx=max(ans1,ans2);
			cout<<tx<<endl;
		}	
	}
	return 0;
}
版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/Keep_Trying_Go/article/details/115920272

智能推荐

Oracle 中 dba_*、all_*、user_* 之间的区别_oracle中dba_开头的user_开头的all_开头的表分别代表什么-程序员宅基地

文章浏览阅读456次。文章目录 1 结论2 示例 1 结论 1. 结论:'权限大小不同': dba_* > all_* > user_* (1) dba_* : 可以访问 '数据库' 中所有的对象(前提:该用户是 dba 用户) (2) all_* :某一用户 '拥有' 的或 '可以访问' 的所有的对象 (3) user_*:某一用户 '拥有' 的所有对象2. 查询是否是 dba 用户 select * from dba_role_privs t where t.granted.._oracle中dba_开头的user_开头的all_开头的表分别代表什么

WPScan初体验_wpscan docker-程序员宅基地

文章浏览阅读1.1w次。近日在朋友圈看某位dalao在Ubuntu上安装WPScan花了一个小时,于是洒家随手在Kali Linux上输入了wpscan,发现Kali里面已经装好了。于是决定玩两把WPScan。WordPress博客平台代码量多,也曾经爆出过大量漏洞。遇到WordPress先用傻瓜式工具扫描一下是一个不错的开始。http://www.cnblogs.com/go2bed/p/6398788.h_wpscan docker

30分钟玩转Markdown_csdn 用markodn-程序员宅基地

文章浏览阅读363次。Markdown-Study1.概述Markdown是一种很简单的标记语言,它有很多优点,编写简单,容易学习,基本上花半个小时的时间就能学会。目前来看,支持Markdown语法的编辑器有很多,包括很多网站也支持了Markdown的文字录入。Markdown从写作到完成,导出格式随心所欲,你可以导出HTML格式的文件用来网站发布,也可以十分方便的导出PDF格式。 很多研发人员写文档时也会选用Markd_csdn 用markodn

【单片机】2.7 复位操作和复位电路_at89c52复位电路原理-程序员宅基地

文章浏览阅读4.6k次,点赞2次,收藏6次。2.7 复位操作和复位电路单片机的初始化操作,给复位脚RST加上大于2个机器周期(即24个时钟振荡周期)的高电平就使AT89S52复位2.7.1 复位操作复位时,PC初始化为0000H,程序从0000H单元开始执行。除系统的正常初始化外,当程序出错(如程序跑飞)或操作错误使系统处于死锁状态时,需按复位键使RST脚为高电平,使AT89S52摆脱“跑飞”或“死锁”状态而重新启动程序。复位操作还对其他一些寄存器有影响,这些寄存器复位时的状态见表2-7。由表2-7可看出,复位时,SP=07H ,而P0_at89c52复位电路原理

Maven公共中央仓库发布自己的Jar包_maven项目如何发布到公共仓库-程序员宅基地

文章浏览阅读2.7w次。#中央仓库发布jar包流程_maven项目如何发布到公共仓库

EasyCode生成后需要的改动_easycode 生成的实体字段名可以修改吗-程序员宅基地

文章浏览阅读256次。生成后需要做的改动:1.Application.ymlserver: port: 8080spring: datasource: url: jdbc:mysql://127.0.0.1:3306/database?useUnicode=true&characterEncoding=UTF-8 username: root password: 123456 type: com.alibaba.druid.pool.DruidDataSource d_easycode 生成的实体字段名可以修改吗

随便推点

SNAP入门教程-1_esa snap 功能-程序员宅基地

文章浏览阅读2w次,点赞35次,收藏212次。SNAP入门教程-11.加载sentinel2数据2.RGB配置1.加载sentinel2数据1.1 打开ESA-SNAP软件1.2 点击File>Open Producet1.3 选择sentinel2数据文件夹内的元文件(.xml)1.4 数据已完成加载1.5 数据包括元文件、索引、矢量、波段、掩码1.6 右击一个波段,点击Properties查看该波段属性1..._esa snap 功能

Office Web Apps Server 搭建(一)_cn_office_web_apps_2013_x64_dvd_1133682.iso-程序员宅基地

文章浏览阅读3.7k次。准备工作按照微软的说法 需要Windows Server 2008及以上.看官方Server 2008 需要Server08 R2 Sp1.NetFrameWork4.5PowerShell 3.0Win7Sp1 和 WinServer08R2Sp1平台更新(KB26670838)卧槽.好复杂 于是我这使用Windows Server 2012 R2那么你需要安装 ..._cn_office_web_apps_2013_x64_dvd_1133682.iso

《21天学通C++》_1 2016.5.23_21天学通c++ 源代码下载-程序员宅基地

文章浏览阅读1.2k次。一、绪论虽然发明 C 语言旨在帮助程序员使用当前新出现的硬件功能,但它得以流行应主要归功于其可移植性和速度C 语言是一种过程化语言,但随着计算机语言进入面向对象时代,Bjarne Stroustrup 于 1981 年发明了 C++,它是发展最快、使用最广泛的编程语言之一除新增了诸如运算符重载和内联函数等功能外,C++还实现了诸如继承(支持多继承)、封装、抽象和多态等面向对象概_21天学通c++ 源代码下载

【赠书福利】人工智能发展的三驾马车-程序员宅基地

文章浏览阅读1k次。提醒!文末有福利哟!说起今年的科技热词,非人工智能(AI)莫属了。“智能+”时代已经到来,那么人工智能是怎么逐步发展起来的呢?先来看看它在历史上经历过的三次浪潮:第一个..._人工智能 三驾马车

C++ vector与map的混合运用_vector 和 map能连用吗-程序员宅基地

文章浏览阅读1.2w次,点赞11次,收藏34次。注意: 在一个A容器存另一个容器B的指针的时候map<int, string>* temMap = it->second;//通过A获取到容器B的指针map<int, string>::iterator itMap = temMap->begin();//创建容器B的迭代器for (; itMap != temMap->end(); itMap++)//遍历cout << " 1map key=" << it->first.c__vector 和 map能连用吗

Mapbox加载天地图CGCS2000矢量瓦片地图服务-程序员宅基地

文章浏览阅读8.5k次。1.背景最近在做天地图的项目,要基于MapBox添加CGCS2000矢量切片数据,但是 Mapbox 只支持web 墨卡托(3857)坐标系的数据。Github有专业用户修改了mapbox-gl的相关代码,支持CGCS2000的切片数据加载,并且修改了相关的mapbox-gl的配套代码,详情请见github网址。https://github.com/cgcs20002.将MapBox部署到本地npm i @cgcs2000/mapbox-gl<!DOCTYPE html><ht_mapbox加载天地图