POJ 2553 The Bottom of a Graph 【scc tarjan】

图论之强连通复习开始- -

题目大意:给你一个有向图,要你求出这样的点集:从这个点出发能到达的点,一定能回到这个点

思路:强连通分量里的显然都可以互相到达 那就一起考虑,缩点后如果一个点有出边,一定不在点集内,因为缩点后是DAG,无环,因此一定不能回到原来的点,所以找到出度为0的点即可

#include<cstdio>

#include<string.h>

#include<math.h>

#include<algorithm>

#include<iostream>

#include<queue>

#define maxn 90000

#define inf 0x3f3f3f3f

using namespace std;

int head[maxn],next[maxn],point[maxn],now=0;

int dfn[maxn],low[maxn],time,col,stack[maxn];

int top,belong[maxn],out[maxn];

bool instack[maxn];

void add(int x,int y)

{

next[++now]=head[x];

head[x]=now;

point[now]=y;

}

void tarjan(int k)

{

int u;

dfn[k]=low[k]=++time;

instack[k]=1;

stack[++top]=k;

for(int i=head[k];i;i=next[i])

{

u=point[i];

if(dfn[u]==0)

{

tarjan(u);

low[k]=min(low[u],low[k]);

}

else if(instack[u])low[k]=min(low[k],low[u]);

}

if(low[k]==dfn[k])

{

++col;

do

{

u=stack[top--];

instack[u]=0;

belong[u]=col;

}while(u!=k);

}

}

int main()

{

int n,m,x,y;

while(1)

{

scanf("%d",&n);

if(n==0)break;

scanf("%d",&m);

now=0;memset(head,0,sizeof(head));

top=0;memset(instack,0,sizeof(instack));

memset(out,0,sizeof(out));

memset(dfn,0,sizeof(dfn));

for(int i=1;i<=m;i++)

{

scanf("%d%d",&x,&y);

add(x,y);

}

for(int i=1;i<=n;i++)if(dfn[i]==0)tarjan(i);

for(int i=1;i<=n;i++)

{

for(int j=head[i];j;j=next[j])

{

int u=point[j];

if(belong[i]!=belong[u])out[belong[i]]++;

}

}

int flag=1;

for(int i=1;i<=n;i++)

{

if(flag && out[belong[i]]==0)

{

printf("%d",i);

flag^=flag;

}

else if(out[belong[i]]==0)printf(" %d",i);

}

printf("\n");

}

return 0;

}

时间: 11-30

POJ 2553 The Bottom of a Graph 【scc tarjan】的相关文章

poj 2553 The Bottom of a Graph【强连通分量求汇点个数】

The Bottom of a Graph Time Limit: 3000MS   Memory Limit: 65536K Total Submissions: 9641   Accepted: 4008 Description We will use the following (standard) definitions from graph theory. Let V be a nonempty and finite set, its elements being called ver

POJ 2553 The Bottom of a Graph

The Bottom of a Graph Time Limit: 3000ms Memory Limit: 65536KB This problem will be judged on PKU. Original ID: 255364-bit integer IO format: %lld      Java class name: Main We will use the following (standard) definitions from graph theory. Let V be

【LCA/tarjan】POJ1470-Closest Common Ancestors

[题意] 给出一棵树和多组查询,求以每个节点为LCA的查询数有多少? [错误点] ①读入的时候,注意它的空格是随意的呀!一开始不知道怎么弄,后来看了DISCUSS区大神的话: 询问部分输入: scanf("%d",&m); for(int i=0;i<m;i++){ scanf(" (%d %d)",&a,&b); } 注意scanf(" 这里有一个空格 ②多组数据啊!注意这句话:The input file contents

【2-SAT(tarjan)】BZOJ1997-[Hnoi2010]Planar

[题目大意]给出一张存在哈密顿回路的无向图,判断是否是平面图.[思路]首先平面图的一个性质:边数<=点数*3-6因为存在哈密顿回路,可以将回路看作是一个圆,考量不再哈密顿回路中的边.如果两天边相交(判断相交可以随意yy一下),那么必然一条在圆内一条在圆外,显然是2-SAT. 1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #inclu

The Bottom of a Graph

                                poj——The Bottom of a Graph Time Limit: 3000MS   Memory Limit: 65536K Total Submissions: 11044   Accepted: 4542 Description We will use the following (standard) definitions from graph theory. Let V be a nonempty and fin

POJ 1041 John&#39;s trip 无向图的【欧拉回路】路径输出

欧拉回路第一题TVT 本题的一个小技巧在于: [建立一个存放点与边关系的邻接矩阵] 1.先判断是否存在欧拉路径 无向图: 欧拉回路:连通 + 所有定点的度为偶数 欧拉路径:连通 + 除源点和终点外都为偶数 有向图: 欧拉回路:连通 + 所有点的入度 == 出度 欧拉路径:连通 + 源点 出度-入度=1 && 终点 入度 - 出度 = 1 && 其余点 入度 == 出度: 2.求欧拉路径 : step 1:选取起点(如果是点的度数全为偶数任意点为S如果有两个点的度数位奇数取一

POJ - 3286 - How many 0&#39;s? 【数位DP】

How many 0's? Time Limit: 1000MS   Memory Limit: 65536KB   64bit IO Format: %I64d & %I64u Description A Benedict monk No.16 writes down the decimal representations of all natural numbers between and including m and n, m ≤ n. How many 0's will he writ

【点分治】【POJ 1741】【cogs 1714】树上的点对

1714. [POJ1741][男人八题]树上的点对 ★★★ 输入文件:poj1741_tree.in 输出文件:poj1741_tree.out 简单对比 时间限制:1 s 内存限制:256 MB [题目描述] 给一棵有n个节点的树,每条边都有一个长度(小于1001的正整数). 定义dist(u,v)=节点u到节点v的最短路距离. 给出一个整数k,我们称顶点对(u,v)是合法的当且仅当dist(u,v)不大于k. 写一个程序,对于给定的树,计算有多少对顶点对是合法的. [输入格式] 输入包含多

POJ 1904:King&#39;s Quest【tarjan】

题目大意:给出一个二分图的完美匹配(王子和公主的烧死名单表),二分图x部和y部均只有n个点,问对于每一个x部的点,他能选择哪些点与之匹配 使得与之匹配后,剩余图的最大匹配仍然是n 思路:这题是大白书379页二分图的压轴题,在图论刷的题还不多时思考过这题,现在想来也不难想 这题引人瞩目的一点便是预先给出了一个二分图的初始匹配 对每个点枚举后增广显然不怎么可行,那么还是图论问题的经典思考方式,点和边各表示什么 题目的输入天然的给出了一个图,但对这题好像没什么用处,于是开始思考把给出的初始匹配的每条边