POJ 2553 The Bottom of a Graph 【scc tarjan】

#include<cstdio>

#include<string.h>

#include<math.h>

#include<algorithm>

#include<iostream>

#include<queue>

#define maxn 90000

#define inf 0x3f3f3f3f

using namespace std;

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

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

bool instack[maxn];

{

point[now]=y;

}

void tarjan(int k)

{

int u;

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

instack[k]=1;

stack[++top]=k;

{

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);

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);

}

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

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

{

{

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;

}

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 - 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. 写一个程序,对于给定的树,计算有多少对顶点对是合法的. [输入格式] 输入包含多