UOJGraph（tarjan缩点+拓扑）

Description

给出 NN 个点, MM 条边的有向图, 对于每个点 vv, 求 A(v)A(v) 表示从点 vv 出发, 能到达的编号最大的点。

Input

第 11 行, 22 个整数 NN, MM。 接下来 MM 行, 每行 22 个整数 UiUi, ViVi, 表示边 ⟨Ui,Vi⟩⟨Ui,Vi⟩。点用 1,2,...,N1,2,...,N 编号。

Output

NN 个整数 A(1),A(2),...,A(N)A(1),A(2),...,A(N)。

Sample

[input]

4 3

1 2

2 4

4 3

[output]

4 4 3 4

Note

对于 60% 的数据, 1 ≤ N, K ≤ 103103;

对于 100% 的数据, 1 ≤ N, M ≤ 105105。

【代码】

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <queue>
#include <stack>
#include <set>
#define maxn 100005
using namespace std;
typedef pair<int,int>pa;
set<pa>mp;
stack<int>s;
int n,m,to[maxn],mx[maxn],from[maxn],pre[maxn],low[maxn],tme=0,fst[maxn],nxt[maxn],scc[maxn];
int scccnt=0,cnt=0,d[maxn],ft[maxn],nt[maxn],ct=0,de[maxn],t[maxn];
void add(int x,int y){to[++cnt]=y;from[cnt]=x;nxt[cnt]=fst[x];fst[x]=cnt;}
void add2(int x,int y){t[++ct]=y;nt[ct]=ft[x];ft[x]=ct;++de[y];}
int get(){
    char c;while(!isdigit(c=getchar()));
    int v=c-48;while(isdigit(c=getchar()))v=v*10+c-48;
    return v;
}
void dfs(int x){
    s.push(x);
    pre[x]=low[x]=++tme;
    for(int i=fst[x];i;i=nxt[i]){
	    if(!pre[to[i]]){
		    dfs(to[i]);
		    low[x]=min(low[x],low[to[i]]);
		}
		else if(!scc[to[i]]){
		    low[x]=min(low[x],pre[to[i]]);
		}
	}
	if(low[x]==pre[x]){
	    ++scccnt;
	    while(1){
		    int y=s.top();s.pop();
		    scc[y]=scccnt;
		    mx[scccnt]=max(mx[scccnt],y);
		    if(y==x)break;
		}
	}
}
void init(){
    n=get(),m=get();int x,y;
    for(int i=1;i<=m;++i){
	    x=get();y=get();
	    add(x,y);++d[y];
	}
	for(int i=1;i<=n;++i)if(!pre[i])dfs(i);  //注意
}
queue<int>q;
void bfs(){
    while(q.size()){
	    int x=q.front();q.pop();
	    for(int i=ft[x];i;i=nt[i]){
		    --de[t[i]];mx[t[i]]=max(mx[t[i]],mx[x]);
		    if(de[t[i]]==0)q.push(t[i]),de[t[i]]=-1;
		}
	}
}
void solveit(){
    for(int i=1;i<=cnt;++i){
		int x=scc[to[i]],y=scc[from[i]];
	    if(x!=y && !mp.count(make_pair(x,y))){     //注意
		    add2(x,y);mp.insert(make_pair(x,y));
		}
	}
	for(int i=1;i<=scccnt;++i)if(de[i]==0)q.push(i),de[i]=-1;
	bfs();
	for(int i=1;i<n;++i)printf("%d ",mx[scc[i]]);
	printf("%d",mx[scc[n]]);
}
int main(){
    init();
    solveit();
    return 0;
}
           

【注意】

*连通块连边时要判断是否为同一连通块

*从1~n未pre[ ]的进入dfs而不是d[ ]为0的