题目链接:
日常水题,题目中已经给出了算法,写个模板即可,不会割点的这里有一篇博客:
难点是每个对可以互换顺序,然后删掉一个点之后它与其他所有点的对都会少1
下面给出代码:
#include#include #include #include #include #include #include using namespace std;inline int rd(){ int x=0,f=1; char ch=getchar(); for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-1; for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0'; return x*f;}inline void write(long long x){ if(x<0) putchar('-'),x=-x; if(x>9) write(x/10); putchar(x%10+'0'); return ;}int n,m;int head[1000006],nxt[1000006],to[1000006];int total=0;void add(int x,int y){ total++; to[total]=y; nxt[total]=head[x]; head[x]=total; return ;}int tot=0;int dfn[1000006],low[1000006],book[1000006];int q[1000006],l=0,r=0;int size[1000006];long long ans[1000006];void Tarjan(int x){ int sum=0; size[x]=1; dfn[x]=low[x]=++tot; for(int e=head[x];e;e=nxt[e]){ if(!dfn[to[e]]){ Tarjan(to[e]); low[x]=min(low[x],low[to[e]]); size[x]+=size[to[e]]; if(low[to[e]]>=dfn[x]){ ans[x]+=(long long)sum*(long long)size[to[e]]; sum+=size[to[e]]; } } else low[x]=min(low[x],dfn[to[e]]); } ans[x]+=(long long)sum*(long long)(n-sum-1); return ;}int main(){ n=rd(),m=rd(); for(int i=1;i<=m;i++){ int x=rd(),y=rd(); add(x,y),add(y,x); } for(int i=1;i<=n;i++) if(!dfn[i]) Tarjan(i); for(int i=1;i<=n;i++) write((ans[i]+n-1)*2),puts(""); return 0;}