【poj2553】The Bottom of a Graph(强连通分量缩点)

时间:2023-02-24 22:49:09

题目链接:http://poj.org/problem?id=2553

【题意】

给n个点m条边构成一幅图,求出所有的sink点并按顺序输出。sink点是指该点能到达的点反过来又能回到该点。

【思路】

不难想象sink点一定是在强连通分量中,而且强连通分量缩点后出度为0,就可以说明该强连通分量内所有的点都是sink点。

之前wa了一发是因为写成了out[i],注意是从缩点构成的dag中找出度为0的点,而不是从原来的图中找。

【ac代码】

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <stack>
#include <vector>
#include <cstring>
using namespace std;
const int N = ;
int low[N], vis[N], dfn[N], col[N], out[N], ans[N];
vector<int>V[N];
stack<int>s;
int n, cnt, num;
void dfs(int u)
{
s.push(u);
vis[u] = ;
dfn[u] = low[u] = ++cnt;
for (int i = ; i < V[u].size(); i++)
{
int v = V[u][i];
if (!dfn[v])
{
dfs(v);
low[u] = min(low[u], low[v]);
}
else if (vis[v])
low[u] = min(low[u], dfn[v]);
}
if (low[u] == dfn[u])
{
int t;
num++;
do
{
t = s.top();
s.pop();
col[t] = num;
vis[t] = ;
}
while (t != u);
}
} void tarjan()
{
int i;
memset(dfn, , sizeof(dfn));
memset(low, , sizeof(low));
memset(vis, , sizeof(vis));
memset(col, , sizeof(col));
while (!s.empty()) s.pop();
cnt = num = ;
for (i = ; i <= n; i++)
if (!dfn[i]) dfs(i);
}
int main()
{
int m, i, j;
while(scanf("%d", &n), n)
{
scanf("%d", &m);
for(i = ; i <= n; i++) V[i].clear();
int a, b;
while(m--)
{
scanf("%d%d", &a, &b);
V[a].push_back(b);
}
tarjan();
memset(out, , sizeof out);
for(i = ; i <= n; i++)
for(j = ; j < V[i].size(); j++)
{
int v = V[i][j];
if(col[i] != col[v]) out[col[i]]++;//该颜色出度+1
}
cnt = ;
for(i = ; i <= n; i++)
if(!out[col[i]]) ans[++cnt] = i;
sort(ans+, ans++cnt);
for(i = ; i < cnt; i++) printf("%d ", ans[i]);
printf("%d\n", ans[cnt]);
}
return ;
}

【poj2553】The Bottom of a Graph(强连通分量缩点)的更多相关文章

  1. poj 2553 The Bottom of a Graph&lpar;强连通分量&plus;缩点&rpar;

    题目地址:http://poj.org/problem?id=2553 The Bottom of a Graph Time Limit: 3000MS   Memory Limit: 65536K ...

  2. POJ-2552-The Bottom of a Graph 强连通分量

    链接: https://vjudge.net/problem/POJ-2553 题意: We will use the following (standard) definitions from gr ...

  3. POJ 2553 The Bottom of a Graph &lpar;强连通分量&rpar;

    题目地址:POJ 2553 题目意思不好理解.题意是:G图中从v可达的全部点w,也都能够达到v,这种v称为sink.然后升序输出全部的sink. 对于一个强连通分量来说,全部的点都符合这一条件,可是假 ...

  4. POJ2553 The Bottom of a Graph(强连通分量&plus;缩点)

    题目是问,一个有向图有多少个点v满足∀w∈V:(v→w)⇒(w→v). 把图的强连通分量缩点,那么答案显然就是所有出度为0的点. 用Tarjan找强连通分量: #include<cstdio&g ...

  5. POJ1236Network of Schools&lbrack;强连通分量&vert;缩点&rsqb;

    Network of Schools Time Limit: 1000MS   Memory Limit: 10000K Total Submissions: 16571   Accepted: 65 ...

  6. POJ1236Network of Schools(强连通分量 &plus; 缩点)

    题目链接Network of Schools 参考斌神博客 强连通分量缩点求入度为0的个数和出度为0的分量个数 题目大意:N(2<N<100)各学校之间有单向的网络,每个学校得到一套软件后 ...

  7. HD2767Proving Equivalences(有向图强连通分量&plus;缩点)

    题目链接 题意:有n个节点的图,现在给出了m个边,问最小加多少边是的图是强连通的 分析:首先找到强连通分量,然后把每一个强连通分量缩成一个点,然后就得到了一个DAG.接下来,设有a个节点(每个节点对应 ...

  8. UVa11324 The Largest Clique(强连通分量&plus;缩点&plus;记忆化搜索)

    题目给一张有向图G,要在其传递闭包T(G)上删除若干点,使得留下来的所有点具有单连通性,问最多能留下几个点. 其实这道题在T(G)上的连通性等同于在G上的连通性,所以考虑G就行了. 那么问题就简单了, ...

  9. ZOJ3795 Grouping(强连通分量&plus;缩点&plus;记忆化搜索)

    题目给一张有向图,要把点分组,问最少要几个组使得同组内的任意两点不连通. 首先考虑找出强连通分量缩点后形成DAG,强连通分量内的点肯定各自一组,两个强连通分量的拓扑序能确定的也得各自一组. 能在同一组 ...

随机推荐

  1. Scrum团队成立3&period;0

    博客园 首页 新随笔 联系 订阅 管理 随笔 - 23  文章 - 0  评论 - 26 0428-Scrum团队成立3.0 ------------------------------3.0---- ...

  2. English Training Material - 01

    Building a relationship Cross-cultural understanding Eye contact In many Western societies, includin ...

  3. AT&amp&semi;T汇编中系统调用和C函数调用的使用

    我的博客:www.while0.com 区别: 系统调用的参数存储在寄存器中,函数调用的则存储在堆栈中. 系统调用使用中断方式,函数调用使用call指令 相同之处: 都有返回值和输入值 返回值都存储在 ...

  4. 安装 CentOS 7 后必做的七件事

    原文 安装 CentOS 7 后必做的七件事 CentOS 是最多人用来运行服务器的 Linux 版本,最新版本是 CentOS 7.当你兴趣勃勃地在一台主机或 VPS 上安装 CentOS 7 后, ...

  5. 学习熟悉箭头函数&comma; 类&comma; 模板字面量&comma; let和const声明

    箭头函数:https://blog.csdn.net/qq_30100043/article/details/53396517 类:https://blog.csdn.net/pcaxb/articl ...

  6. 01&lowbar; if 练习

    prompt()        弹出一个对话框,该对话框中会带有一个文本框,用户可以在文本框中输入一段内容. 该函数需要一个字符串作为参数,用作对话框的提示文字. 用户输入内容,将会作为函数返回值.可 ...

  7. spring 读取yaml配置文件

    从Spring框架4.1.0增加了对YAML的支持,Spring框架4.1.0 maven POM具有Snakeyaml依赖性  . 您可以在Spring Boot应用中使用两种方式加载YAML: 1 ...

  8. Linux Crontab及使用salt进行管理

    一.引言: 最近无意之间看到salt有一个cron的模块,今天就在这里介绍linux crontab以及通过salt的cron对crontab的管理. 二.Linux crontab的介绍: cron ...

  9. Object-c 构造、析构函数

    一.构造函数 在OC中凡是已init开头的函数我们都称之为构造函数,在声明构造函数的时候,不带参数的一般直接声明为“-(id)init”,带参数的一般声明为“-(id)initWith...”. @i ...

  10. 项目管理工具maven(二)

    2 整合ssh框架 2.1 依赖传递 只添加了一个struts2-core依赖,发现项目中出现了很多jar, 这种情况 叫 依赖传递 2.2 依赖版本冲突的解决 1. 第一声明优先原则 <dep ...