Byteotia城市有n个 towns， m条双向roads. 每条 road 连接 两个不同的 towns ,没有重复的road. 所有towns连通。
输入n和m。( n<=100000 ，m<=500000 )
输出n个数，其中第i个整数表示把与节点i关联的所有边去掉之后（不去掉节点i本身），无向图中有多少个有序点对(x,y),满足x和y不连通。
5 5
1 2
2 3
1 3
3 4
4 58
8
16
14
8时间限制：1s
空间限制：128MB
not finished：
#include<cstdio> #include<algorithm> #include<iostream> #include<cstring> #include<cstdlib> #include<cmath> using namespace std; const int maxn=1e5+5; const int maxm=5e5+5; inline int read(){ int a=0;bool b=1;char x=getchar(); while(x<‘0‘||‘9‘<x){ if(x==‘-‘)b=0; x=getchar(); } while(‘0‘<=x && x<=‘9‘){ a=(a<<3)+(a<<1)+x-‘0‘; x=getchar(); } return b ? a : -a ; } int first[maxn],next[maxm*2],to[maxm*2],edge_count; inline void add(int x,int y){ edge_count++; to[edge_count]=y; next[edge_count]=first[x]; first[x]=edge_count; } int pre[maxn],low[maxn],Time,size[maxn],cnct[maxn]; int ans[maxn]; //size表示搜索树上i节点下方节点数 void tarjan(int root){ pre[root]=low[root]=++Time; size[root]=1; int temp=0; for(int i=first[roor];i;i=next[i]){ int v=to[i]; if(!pre[v]){ tarjan(v); size[root] low[root]=min(low[root],low[v]); if(pre[root]<=low[v]){ temp++; if(root!=1 || temp>1){ } } } else low[root]=min(low[root],); } } int n,m; int main() { n=read();m=read(); const int N=n+n-2; for(int i=1,a,b;i<=m;i++){ a=read();b=read(); add(a,b);add(b,a); } tarjan(1); for(int i=1;i<=n;i++){ printf("%d\n",ans[i]+N); } return 0; }
原文：https://www.cnblogs.com/a-blog-of-taojiayi-2003/p/10770996.html