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

• 2018-02-21
• 0
• 0

N 个整数

输入输出样例

4 3
1 2
2 4
4 3

4 4 3 4

• 对于 60% 的数据，

• 对于 100% 的数据，

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;
}
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)
}
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
(该域名已过期且被抢注。。)
darkleafin.github.io

49750

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