题目链接: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(强连通分量缩点)的更多相关文章
-
poj 2553 The Bottom of a Graph(强连通分量+缩点)
题目地址:http://poj.org/problem?id=2553 The Bottom of a Graph Time Limit: 3000MS Memory Limit: 65536K ...
-
POJ-2552-The Bottom of a Graph 强连通分量
链接: https://vjudge.net/problem/POJ-2553 题意: We will use the following (standard) definitions from gr ...
-
POJ 2553 The Bottom of a Graph (强连通分量)
题目地址:POJ 2553 题目意思不好理解.题意是:G图中从v可达的全部点w,也都能够达到v,这种v称为sink.然后升序输出全部的sink. 对于一个强连通分量来说,全部的点都符合这一条件,可是假 ...
-
POJ2553 The Bottom of a Graph(强连通分量+缩点)
题目是问,一个有向图有多少个点v满足∀w∈V:(v→w)⇒(w→v). 把图的强连通分量缩点,那么答案显然就是所有出度为0的点. 用Tarjan找强连通分量: #include<cstdio&g ...
-
POJ1236Network of Schools[强连通分量|缩点]
Network of Schools Time Limit: 1000MS Memory Limit: 10000K Total Submissions: 16571 Accepted: 65 ...
-
POJ1236Network of Schools(强连通分量 + 缩点)
题目链接Network of Schools 参考斌神博客 强连通分量缩点求入度为0的个数和出度为0的分量个数 题目大意:N(2<N<100)各学校之间有单向的网络,每个学校得到一套软件后 ...
-
HD2767Proving Equivalences(有向图强连通分量+缩点)
题目链接 题意:有n个节点的图,现在给出了m个边,问最小加多少边是的图是强连通的 分析:首先找到强连通分量,然后把每一个强连通分量缩成一个点,然后就得到了一个DAG.接下来,设有a个节点(每个节点对应 ...
-
UVa11324 The Largest Clique(强连通分量+缩点+记忆化搜索)
题目给一张有向图G,要在其传递闭包T(G)上删除若干点,使得留下来的所有点具有单连通性,问最多能留下几个点. 其实这道题在T(G)上的连通性等同于在G上的连通性,所以考虑G就行了. 那么问题就简单了, ...
-
ZOJ3795 Grouping(强连通分量+缩点+记忆化搜索)
题目给一张有向图,要把点分组,问最少要几个组使得同组内的任意两点不连通. 首先考虑找出强连通分量缩点后形成DAG,强连通分量内的点肯定各自一组,两个强连通分量的拓扑序能确定的也得各自一组. 能在同一组 ...
随机推荐
-
Scrum团队成立3.0
博客园 首页 新随笔 联系 订阅 管理 随笔 - 23 文章 - 0 评论 - 26 0428-Scrum团队成立3.0 ------------------------------3.0---- ...
-
English Training Material - 01
Building a relationship Cross-cultural understanding Eye contact In many Western societies, includin ...
-
AT&;T汇编中系统调用和C函数调用的使用
我的博客:www.while0.com 区别: 系统调用的参数存储在寄存器中,函数调用的则存储在堆栈中. 系统调用使用中断方式,函数调用使用call指令 相同之处: 都有返回值和输入值 返回值都存储在 ...
-
安装 CentOS 7 后必做的七件事
原文 安装 CentOS 7 后必做的七件事 CentOS 是最多人用来运行服务器的 Linux 版本,最新版本是 CentOS 7.当你兴趣勃勃地在一台主机或 VPS 上安装 CentOS 7 后, ...
-
学习熟悉箭头函数, 类, 模板字面量, let和const声明
箭头函数:https://blog.csdn.net/qq_30100043/article/details/53396517 类:https://blog.csdn.net/pcaxb/articl ...
-
01_ if 练习
prompt() 弹出一个对话框,该对话框中会带有一个文本框,用户可以在文本框中输入一段内容. 该函数需要一个字符串作为参数,用作对话框的提示文字. 用户输入内容,将会作为函数返回值.可 ...
-
spring 读取yaml配置文件
从Spring框架4.1.0增加了对YAML的支持,Spring框架4.1.0 maven POM具有Snakeyaml依赖性 . 您可以在Spring Boot应用中使用两种方式加载YAML: 1 ...
-
Linux Crontab及使用salt进行管理
一.引言: 最近无意之间看到salt有一个cron的模块,今天就在这里介绍linux crontab以及通过salt的cron对crontab的管理. 二.Linux crontab的介绍: cron ...
-
Object-c 构造、析构函数
一.构造函数 在OC中凡是已init开头的函数我们都称之为构造函数,在声明构造函数的时候,不带参数的一般直接声明为“-(id)init”,带参数的一般声明为“-(id)initWith...”. @i ...
-
项目管理工具maven(二)
2 整合ssh框架 2.1 依赖传递 只添加了一个struts2-core依赖,发现项目中出现了很多jar, 这种情况 叫 依赖传递 2.2 依赖版本冲突的解决 1. 第一声明优先原则 <dep ...