Byteotia城市有n个 towns m条双向roads. 每条 road 连接 两个不同的 towns ,没有重复的road. 所有towns连通。
输入n<=100000 m<=500000及m条边
输出n个数，代表如果把第i个点去掉，将有多少对点不能互通。
点对是有序的、去掉的点也要算
对于一个去掉的点，要产生除了包括其本身在内的点对，那该点一定是割点
所以就求割点啊，每个连通块一顿乘就好啦
先随手放一个求割点
void tarjan(int u) { dfn[u]=low[u]=++cnt;size[u]=1; int tmp=0; for(int i=last[u];i;i=e[i].nt) { if(e[i].to==fa[u])continue; if(!dfn[e[i].to]) { son[u]++;fa[e[i].to]=u;tarjan(e[i].to);size[u]+=size[e[i].to]; //在外面加son的绝壁只有我这样的傻叉 low[u]=min(low[u],low[e[i].to]); if(low[e[i].to]>=dfn[u]) iscut[u]=1; } else if(dfn[e[i].to]<low[u]) low[u]=dfn[e[i].to]; } if(fa[u]==0&&son[u]<=1)iscut[u]=0; } 没有调好虚。。。代码：
#include<cmath> #include<ctime> #include<cstdio> #include<cstring> #include<cstdlib> #include<complex> #include<iostream> #include<algorithm> #include<iomanip> #include<vector> #include<string> #include<queue> #include<set> #include<map> using namespace std; typedef long long ll; inline int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch<='9'&&ch>='0'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();} return x*f; } const int N=100100; int n,m,ecnt,last[N],dfn[N],low[N],size[N],son[N],fa[N],cnt; bool iscut[N]; ll ans[N]; struct EDGE{int to,nt;}e[N<<4]; inline void add(int u,int v) {e[++ecnt]=(EDGE){v,last[u]};last[u]=ecnt;} void tarjan(int u) { dfn[u]=low[u]=++cnt;size[u]=1; int tmp=0; for(int i=last[u];i;i=e[i].nt) { if(e[i].to==fa[u])continue; if(!dfn[e[i].to]) { fa[e[i].to]=u;tarjan(e[i].to);size[u]+=size[e[i].to]; low[u]=min(low[u],low[e[i].to]); if(low[e[i].to]>=dfn[u]) { ans[u]+=tmp*size[e[i].to]; tmp+=size[e[i].to]; } } else if(dfn[e[i].to]<low[u]) low[u]=dfn[e[i].to]; } ans[u]+=ll(n-1-tmp)*tmp; } int main() { n=read();m=read(); for(int i=1;i<=m;i++) {int u=read(),v=read();add(u,v);add(v,u);} tarjan(1); for(int i=1;i<=n;i++) printf("%lld\n",(ans[i]+n-1)<<1);; return 0; } /* 5 5 1 2 2 3 1 3 3 4 4 5 8 8 16 14 8 */