[洛谷春令营 D7T1] 图的遍历【Tarjan缩点+记忆化搜索】

  • 2018-02-21
  • 0
  • 0

题目描述

给出  个点, 条边的有向图,对于每个点 ,求  表示从点  出发,能到达的编号最大的点。

输入输出格式

输入格式:

第 1 行,2 个整数 

接下来  行,每行 2 个整数  ,表示边  。点用  编号。

输出格式:

N 个整数 

输入输出样例

输入样例#1:

4 3
1 2
2 4
4 3

输出样例#1:

4 4 3 4

说明

• 对于 60% 的数据,

• 对于 100% 的数据,

Solution:

这是一道 比较水的 图论题。

第一思路是记忆化搜索,理论复杂度 O(N)。

然而我们发现,记忆化搜索可以看作动规,只能在 DAG 上进行。

而本题并未保证给出的有向图无,所以需要先用 Tarjan 缩点。

Code: O(N+M) [9054K, 92MS]

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std;

inline void getint(int &num){
	char ch;
	while(!isdigit(ch = getchar()));
	num = ch - '0';
	while(isdigit(ch = getchar())) num = num * 10 + ch - '0';
}

int N, M;

struct Edge{
	int np;
	Edge *nxt;
};

struct Graph{
	Edge E[100005], *V[100005];
	int tope;
	
	inline void addedge(int u, int v){
		E[++tope].np = v;
		E[tope].nxt = V[u], V[u] = &E[tope];
	}
} G, C;

int dfn[100005], dfstime = 0, low[100005];
int stk[100005], tops = 0, stat[100005];
int col[100005], topc = 0;

inline void Tarjan(int u){
	low[u] = dfn[u] = ++dfstime;
	stk[++tops] = u, stat[u] = 1;
	for(register Edge *ne = G.V[u]; ne; ne = ne->nxt){
		if(stat[ne->np] == 0){
			Tarjan(ne->np);
			low[u] = min(low[u], low[ne->np]);
		}
		else if(stat[ne->np] == 1) low[u] = min(low[u], dfn[ne->np]);
	}
	if(low[u] == dfn[u]){
		topc++;
		while(stk[tops + 1] != u){
			col[stk[tops]] = topc;
			stat[stk[tops--]] = 2;
		}
	}
}

int mxid[100005], A[100005];

inline int dfs(int u){
	if(A[u]) return A[u];
	A[u] = mxid[u];
	for(register Edge *ne = C.V[u]; ne; ne = ne->nxt)
		A[u] = max(A[u], dfs(ne->np));
	return A[u];
}

int main(){
	getint(N), getint(M);
	for(register int i = 1; i <= M; i++){
		int u, v;
		getint(u), getint(v), G.addedge(u, v);
	}
	for(register int i = 1; i <= N; i++) if(stat[i] == 0) Tarjan(i);
	for(register int i = 1; i <= N; i++){
		mxid[col[i]] = max(mxid[col[i]], i);
		for(register Edge *ne = G.V[i]; ne; ne = ne->nxt)
			C.addedge(col[i], col[ne->np]);
	}
	memset(stat, 0, sizeof(stat));
	for(register int i = 1; i <= N; i++) if(stat[i] == 0) dfs(i);
	for(register int i = 1; i < N; i++) printf("%d ", A[col[i]]);
	printf("%d\n", A[col[N]]);
	return 0;
}

评论

还没有任何评论,你来说两句吧



新博客地址: darkleafin.cf

常年不在线的QQ:
49750

不定期更新的GitHub:
https://github.com/Darkleafin


OPEN AT 2017.12.10

如遇到代码不能正常显示的情况,请刷新页面。
Please refresh the page if the code cannot be displayed normally.


发现一个优美的网站:
https://visualgo.net/en
















- Theme by Qzhai