Tarjan求调 30pts WA+TLE 马蜂良好
查看原帖
Tarjan求调 30pts WA+TLE 马蜂良好
572133
潘德理2010楼主2024/1/6 21:23
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll ans;
int n,m;
int l[100050],d[100050],s[100050],c,ro,t,ct[100050],te;
int h[500050],ne[500050],fr[500050],to[500050],r=1;
vector<int> e[100050];
priority_queue<int> q[100050];
int fa[100050],vis[100050],w[100050];
void add(int a,int b){
	fr[++r]=a,to[r]=b;
	ne[r]=h[a];
	h[a]=r;
}
int a,b;
void tarj(int u){
	l[u]=d[u]=++c;
	int son=0;
	for(int i=h[u];i;i=ne[i]){
		int v=to[i];
		if(!d[v]){
			son++;
			tarj(v);
			l[u]=min(l[u],l[v]);
			if(l[v]>=d[u]&&u!=ro) ct[u]=1;
		}
		else l[u]=min(l[u],d[v]);
	}
	if(son>=2&&u==ro) ct[u]=1;
}
void dfs(int u){
	s[u]=t;
	for(int i=h[u];i;i=ne[i]){
		int v=to[i];
		if(s[v]||ct[v]||ct[u]) continue;
		dfs(v);
	}
}
void se(int u){
	vis[u]=1;
	for(int i=0;i<int(e[u].size());i++){
		int v=e[u][i];
		if(vis[v]) continue;
		fa[v]=u;
		se(v);
		w[u]+=w[v];
	}
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++){
		scanf("%d%d",&a,&b);
		add(a,b);
		add(b,a);
	}
	for(int i=1;i<=n;i++){
		if(!d[i]){
			ro=i;
			tarj(i);
		}
	}
	for(int i=1;i<=n;i++){
		if(!s[i]){
			t++;
			dfs(i);
		}
	}
	for(int i=1;i<=n;i++){
		w[s[i]]++;
	}
	for(int i=2;i<=r;i++){
		int u=fr[i],v=to[i];
		if(s[u]!=s[v]){
			q[s[u]].push(s[v]);
		}
	}
	for(int i=1;i<=t;i++){
		while(!q[i].empty()){
			int te=q[i].top();
			while(!q[i].empty()&&q[i].top()==te) q[i].pop();
			e[i].push_back(te);
		}
	}
	se(1);
	for(int i=1;i<=n;i++){
		int u=s[i];
		ans=2*n-2;
		if(ct[i]){
			for(int j=0;j<int(e[u].size());j++){
				int v=e[u][j];
				ll ds;
				if(v==fa[u]) ds=n-w[u];
				else ds=w[v];
				ans+=(ds)*(n-ds-1);
			}
		}
		printf("%lld\n",ans);
	}
}
2024/1/6 21:23
加载中...