rt。

这是正规的 Tarjan 吗？

它的时间复杂度？

它的正确性？

#include<bits/stdc++.h>
using namespace std;
struct Side
{
	int to;
	int next_side;
};
struct Fdlks
{
	Side sds[200012];
	int first[10012];
	int m;
	void init()
	{
		m=0;
		memset(sds,0,sizeof sds);
		memset(first,-1,sizeof first);
		for(int i=0;i<=200011;i++)
			sds[i].next_side=-1;
	}
	void add(int from,int to)
	{
		m++;
		sds[m].to=to;
		sds[m].next_side=first[from];
		first[from]=m;
	}
}res;
struct Rtt
{
	int ldrs[10012],sz[10012];
	stack<int>s;
	void init()
	{
		memset(ldrs,0,sizeof ldrs);
		memset(sz,0,sizeof sz);
		for(int i=1;i<=10000;i++)
			ldrs[i]=i,sz[i]=1;
	}
	void mrg(int x,int y)
	{
    	while(ldrs[y]!=y) s.push(y),y=ldrs[y];
    	s.push(y);
    	while(ldrs[x]!=x) s.push(x),x=ldrs[x];
    	s.push(x);
    	if(sz[y]>sz[x]) swap(x,y);
    	while(!s.empty())
    	{
        	ldrs[s.top()]=x;
	        s.pop();
    	}
    	sz[x]+=sz[y];
	}
	int want(int x)
	{
		while(ldrs[x]!=x) s.push(x),x=ldrs[x];
		while(!s.empty())
		{
			ldrs[s.top()]=x;
			s.pop();
		}
		return x;
	}
};
struct Oof
{
	bool alr[10012];
	Rtt rtt;
	Fdlks ori,res;
	stack<pair<int,int>>s;
	void init()
	{
		memset(alr,0,sizeof alr);
		rtt.init();
		ori.init();
		res.init();
		s.push(make_pair(-1,-1));
	}
	void add(int from,int to,int drct)
	{
		ori.add(from,to);
		if(!drct) ori.add(to,from);
	}
	void set_rts(int x)
	{
		if(alr[rtt.want(x)])
		{
			int k=rtt.want(x);
			while(s.top().second!=k)
			{
				alr[s.top().second]=false;
				rtt.mrg(s.top().first,x);
				s.pop();
			}
			pair<int,int> tmp=s.top();
			alr[tmp.second]=false;
			s.pop();
			tmp.second=rtt.want(x);
			s.push(tmp);
			alr[rtt.want(x)]=true;
			return;
		}
		alr[rtt.want(x)]=true;
		s.push(make_pair(x,rtt.want(x)));
		int i=ori.first[rtt.want(x)];//
		if(i==-1)
		{
			s.pop();
			alr[rtt.want(x)]=false;
		}
		while(i!=-1)
		{
			if(ori.sds[i].to!=x) set_rts(ori.sds[i].to);
			i=ori.sds[i].next_side;
		}
		if(s.top().first==x)
		{
		    s.pop();
		    alr[rtt.want(x)]=false;
		}
	}
	void gnrs(int n)
	{
	    res=ori;
	    for(int j=1;j<=n;j++)
	    {
		    int i=res.first[j];
		    while(i!=-1)
		    {
		    	res.sds[i].to=rtt.want(res.sds[i].to);
		    	i=res.sds[i].next_side;
		    }
	    }
	    for(int j=1;j<=n;j++)
	    {
	    	if(rtt.want(j)==j) continue;
	    	int i=res.first[j];
	    	while(i!=-1)
	    	{
	    		res.add(rtt.want(j),res.sds[i].to);
	    		i=res.sds[i].next_side;
	    	}
	    	res.first[j]=-1;
	    }
	}
}oof;
int a[10012];
bool st[10012];
int request[10012];
int ansans[10012];
queue<int>q;
int main()
{
	oof.init();
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		cin>>a[i];
	for(int i=1;i<=m;i++)
	{
		int x,y;
		cin>>x>>y;
		oof.add(x,y,1);
	}
	for(int i=1;i<=n;i++)
		oof.set_rts(i);
	oof.gnrs(n);
	for(int i=1;i<=n;i++)
		if(oof.rtt.want(i)!=i) a[oof.rtt.want(i)]+=a[i];
	for(int i=1;i<=n;i++)
		st[i]=true;
	for(int j=1;j<=n;j++)
	{
		if(oof.rtt.want(j)!=j)
		{
			st[j]=false;
			continue;
		}
		int i=oof.res.first[j];
		while(i!=-1)
		{
			if(oof.res.sds[i].to!=j) st[oof.res.sds[i].to]=false;
			i=oof.res.sds[i].next_side;
		}
	}
	int ans=0;
	for(int i=1;i<=n;i++)
		if(st[i])
		{
			q.push(i);
			ansans[i]=a[i];
			request[i]=true;
			ans=max(ans,a[i]);
		}
	while(!q.empty())
	{
		int now=q.front();
		request[now]=false;
		int i=oof.res.first[now];
		while(i!=-1)
		{
			if(oof.res.sds[i].to!=now)
			{
				if(!request[oof.res.sds[i].to]) q.push(oof.res.sds[i].to);
				ansans[oof.res.sds[i].to]=a[oof.res.sds[i].to]+ansans[now];
				ans=max(ans,ansans[oof.res.sds[i].to]);
			}
			i=oof.res.sds[i].next_side;
		}
		q.pop();
	}
	cout<<ans;
	return 0;
}