Description

给出一个有向图, 要求出至少从哪几个点出发, 能不漏地经过所有节点。

再求出至少加几条边, 才能使图变成一个强联通分量

Solution

求出所有强联通分量, 形成一个有向无环图, 第一问题就是求出有多少强联通分量的入度为 $0$

第二个问题就是求出 入度为$0 $和 出度为$0$  的强联通分量的数量  的 最大值, 想象一下就可以了。

在整个图都是强联通分量下, 第二个问题答案为 $0$。

Code

 #include<cstdio>
#include<cstring>
#include<algorithm>
#define rd read()
#define rep(i,a,b) for(int i = (a); i <= (b); ++i)
#define per(i,a,b) for(int i = (a); i >= (b); --i)
using namespace std; const int N = ;
const int M = 6e6; int head[N], tot;
int col[N], col_num, size[N];
int n, dfn[N], low[N], cnt, vis[N];
int st[N], tp, ans1, ans2;
int chu[N], ru[N]; struct edge {
int nxt, to, fr;
}e[M]; int read() {
int X = , p = ; char c = getchar();
for(; c > '' || c < ''; c = getchar()) if(c == '-') p = -;
for(; c >= '' && c <= ''; c = getchar()) X = X * + c - '';
return X * p;
} void add(int u, int v) {
e[++tot].to = v;
e[tot].nxt = head[u];
e[tot].fr = u;
head[u] = tot;
} void tarjan(int u) {
dfn[u] = low[u] = ++cnt;
st[++tp] = u;
vis[u] = ;
for(int i = head[u]; i; i = e[i].nxt) {
int nt = e[i].to;
if(!dfn[nt]) tarjan(nt), low[u] = min(low[u], low[nt]);
else if(vis[nt]) low[u] = min(low[u], dfn[nt]);
}
if(dfn[u] == low[u]) {
col_num++;
for(; tp;) {
int nt = st[tp--];
vis[nt] = ;
col[nt] = col_num;
if(nt == u) break;
}
}
} int main()
{
n = rd;
for(int i = ; i <= n; ++i) {
for(; ;) {
int x = rd;
if(!x) break;
add(i, x);
}
}
for(int i = ; i <= n; ++i)
if(!dfn[i]) tarjan(i);
for(int i = ; i <= tot; ++i) {
int x = e[i].fr, y = e[i].to;
if(col[x] == col[y]) continue;
ru[col[y]]++; chu[col[x]]++;
}
for(int i = ; i <= col_num; ++i)
if(!ru[i]) ans1++;
printf("%d\n", ans1);
if(col_num == ) return printf("0\n"), ;
for(int i = ; i <= col_num; ++i)
if(!chu[i]) ans2++;
printf("%d\n", max(ans1, ans2));
}

最新文章

  1. Spark运行模式与Standalone模式部署
  2. 编译Ansj之Solr插件
  3. iOS实现简书的账号识别方式(正则表达式)
  4. phpstorm 激活
  5. SqlServer 在创建数据库时候指定的初始数据库大小是不能被收缩的
  6. SVN上传文件注意事项-------------------养成良好的项目文件上传习惯
  7. 动态修改 NodeJS 程序中的变量值
  8. 判断一个Bitmap图像是否是.9图
  9. 读《编写高质量代码:改善JavaScript程序的188个建议》2
  10. c#写日志方法
  11. jQuery.extend函数详细用法!
  12. mysql数据库封装和 分页查询
  13. 谈谈一些有趣的CSS题目(十三)-- 巧妙地制作背景色渐变动画!
  14. Java并发Fork-Join框架原理解析
  15. Laragon+PHP7中开启xdebug
  16. mac 装5.6版本mysql 设置密码
  17. Source Insight 4.0 文件类型、编码格式、tab转空格、tab键自动补全设置。。。
  18. Orchard运用 - 网站样例
  19. HTML5拖拽功能中 dataTransfer对象详解
  20. 集成淘宝sdk

热门文章

  1. java-学习5
  2. vuejs 组件通讯
  3. mybatis 插入返回自增后的id
  4. jdbc连接mysql/oracle数据库
  5. hdoj1013(数根,大数,九余数算法)
  6. TOJ 2755 国际象棋(搜索)
  7. SVN集成compare4比较软件
  8. ios应用内嵌h5页面数据自动变色识别为手机号码的解决方法——手机号码拨号禁用IOS手机页面数字自动识别为手机号
  9. TZOJ 1937 Hie with the Pie(floyd+状压dp)
  10. [剑指Offer]52-两个链表的第一个公共节点