求助:WA#6#10(代码有注释命名意义,计算思路))
查看原帖
求助:WA#6#10(代码有注释命名意义,计算思路))
409518
Zzz_yigui楼主2023/10/17 14:55

求求大佬帮忙康康或给组hack QAQ

#include<bits/stdc++.h>
using namespace std;
int n,m,u,v,dt[100005],low[100005],ss[100005],cnt,rt;//dt:dfs序,low[]tarjan的low,ss树大小,rt:根,cnt:dfs序记录 
long long int ans[100005];
vector <int> mp[100005];
void tj(int x){
	ss[x]++;              //自身 
	dt[x]=++cnt;
	low[x]=cnt;
	int t=n-1; 
	for(int i=0;i<mp[x].size();i++){
		if(!dt[mp[x][i]]){
			tj(mp[x][i]);
			if(low[mp[x][i]]>=dt[x]){
				t-=ss[mp[x][i]];                        //统计非子产生连通块大小 
				ans[x]+=ss[mp[x][i]]*(n-ss[mp[x][i]]);  //每个连通块内节点都可以与非连通块节点产生一个(x,y) 只记一次不会数重 
			}
			low[x]=min(low[x],low[mp[x][i]]);
			ss[x]+=ss[mp[x][i]];
		}
		else low[x]=min(low[x],dt[mp[x][i]]);
	} 
	ans[x]+=n-1;                                        //自身被割开 
	ans[x]+=t*(n-t);                                    //非子产生的连通块 
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		cin>>u>>v;
		mp[u].push_back(v);
		mp[v].push_back(u);
	}
	rt=1;
	tj(1);
	for(int i=1;i<=n;i++){
		cout<<ans[i]<<endl;
	}
	return 0;
}
2023/10/17 14:55
加载中...