【NOIP模拟题】Graph(tarjan+dfs)
2024-10-19 11:51:01
似乎我搞得太复杂了?
先tarjan缩点然后dfs就行了QAQ。
(我不说我被一个sb错调了半个小时。。。。不要以为缩点后dfs就可以肆无忌惮的不加特判判vis了。。
bfs的做法:减反图,然后从大到小枚举(贪心),标记即可
#include <cstdio>
#include <cstring>
#include <cmath>
#include <string>
#include <iostream>
#include <algorithm>
#include <queue>
#include <set>
#include <vector>
#include <map>
using namespace std;
typedef long long ll;
#define pii pair<int, int>
#define mkpii make_pair<int, int>
#define pdi pair<double, int>
#define mkpdi make_pair<double, int>
#define pli pair<ll, int>
#define mkpli make_pair<ll, int>
#define rep(i, n) for(int i=0; i<(n); ++i)
#define for1(i,a,n) for(int i=(a);i<=(n);++i)
#define for2(i,a,n) for(int i=(a);i<(n);++i)
#define for3(i,a,n) for(int i=(a);i>=(n);--i)
#define for4(i,a,n) for(int i=(a);i>(n);--i)
#define CC(i,a) memset(i,a,sizeof(i))
#define read(a) a=getint()
#define print(a) printf("%d", a)
#define dbg(x) cout << (#x) << " = " << (x) << endl
#define error(x) (!(x)?puts("error"):0)
#define printarr2(a, b, c) for1(_, 1, b) { for1(__, 1, c) cout << a[_][__]; cout << endl; }
#define printarr1(a, b) for1(_, 1, b) cout << a[_] << '\t'; cout << endl
inline const int getint() { int r=0, k=1; char c=getchar(); for(; c<'0'||c>'9'; c=getchar()) if(c=='-') k=-1; for(; c>='0'&&c<='9'; c=getchar()) r=r*10+c-'0'; return k*r; }
inline const int max(const int &a, const int &b) { return a>b?a:b; }
inline const int min(const int &a, const int &b) { return a<b?a:b; } const int N=1e5+10;
int m, mx[N], LL[N], FF[N], vis[N], tot, scc, st[N], fa[N], top;
struct Gr {
int ihead[N], cnt, n;
struct dat { int next, to; }e[N];
void add(int u, int v) { e[++cnt].next=ihead[u]; ihead[u]=cnt; e[cnt].to=v; }
void tarjan() { for1(i, 1, n) if(!FF[i]) tarjan(i); }
void tarjan(int x) {
LL[x]=FF[x]=++tot; vis[x]=1; st[++top]=x;
for(int i=ihead[x]; i; i=e[i].next) {
int y=e[i].to;
if(!FF[y]) {
tarjan(y);
LL[x]=min(LL[x], LL[y]);
}
else if(vis[y] && FF[y]<LL[x]) LL[x]=FF[y];
}
if(FF[x]==LL[x]) {
++scc;
int y;
do {
y=st[top--];
vis[y]=0;
fa[y]=scc;
mx[scc]=max(mx[scc], y);
} while(y!=x);
}
}
void dfs() { CC(vis, 0); for1(i, 1, n) if(!vis[i]) dfs(i); }
void dfs(int x) {
if(vis[x]) return; //这个我就不说了,坑。。。
vis[x]=1;
for(int i=ihead[x]; i; i=e[i].next) {
dfs(e[i].to);
mx[x]=max(mx[x], mx[e[i].to]);
}
}
}G, g; int main() {
read(G.n); read(m);
for1(i, 1, m) { int u=getint(), v=getint(); G.add(u, v); }
G.tarjan();
g.n=scc;
for1(x, 1, G.n) for(int i=G.ihead[x]; i; i=G.e[i].next) if(fa[x]!=fa[G.e[i].to]) g.add(fa[x], fa[G.e[i].to]);
g.dfs();
for1(i, 1, G.n) printf("%d ", mx[fa[i]]);
return 0;
}
【题目描述】
给出 N 个点,M 条边的有向图,对于每个点 v,求 A(v) 表示从点 v 出发,能到达的编号最大的点。
【输入格式】
第 1 行,2 个整数 N,M。 接下来 M 行,每行 2 个整数 Ui,Vi,表示边 ⟨Ui,Vi⟩。点用 1,2,...,N 编号。
【输出格式】
N 个整数 A(1),A(2),...,A(N)。
【样例输入】
4 3
1 2
2 4
4 3
【样例输出】
4 4 3 4
【数据范围】
对于 60% 的数据,1 ≤ N,K ≤ 10^3
对于 100% 的数据,1 ≤ N,M ≤ 10^5。
最新文章
- java并发控制:lock
- 单页面网站关于id冲突的解决办法
- Jsp c标签数值格式化
- Windows创建文件链接
- C++标准文档下载
- 命令 ";sudo -H"; 中的这个 ";H"; 什么作用?
- C# 日期格式化的中的 正斜杠的问题
- jQuery validate运作流程以及重复提示错误问题
- Mustache学习
- Objective-C和Swift
- ASP.NET Core 认证与授权[5]:初识授权
- hibernate之事务处理
- mtr命令详解诊断网络路由
- linux软件管理 源码包
- 一个简单的gridlayout栗子
- No suitable servers found (`serverselectiontryonce` set): [Failed connecting to &#39;115.28.161.44:27017&#39;: Connection timed out] php mongodb 异常
- sqlserver 中WITH NOLOCK、HOLDLOCK、UPDLOCK、TABLOCK、TABLOCKX
- 【Java】异常类处理层次
- js ==与===区别(非严格相等与严格相等)
- python 根据年月日,计算是这一年中的第几天