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

• 2018-02-21
• 0
• 0

题目描述

给出 $N$ 个点，$M$ 条边的有向图，对于每个点 $v$，求 $A(v)$ 表示从点 $v$ 出发，能到达的编号最大的点。

输入输出格式

输入格式：

第 1 行，2 个整数 $N,M$。

接下来 $M$ 行，每行 2 个整数 U_i​, V_i​ ，表示边 (U_i, V_i​) 。点用 $1,2,\cdots ,N$ 编号。

输出格式：

N 个整数 $A(1),A(2),\cdots ,A(N)$。

输入输出样例

4 3
1 2
2 4
4 3

4 4 3 4

说明

• 对于 60% 的数据，1≤N, M≤10³；

• 对于 100% 的数据，1≤N, M≤10⁵。

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