Description
Byteotia城市有n个 towns, m条双向roads. 每条 road 连接 两个不同的 towns ,没有重复的road. 所有towns连通。
Input
输入n和m。( n<=100000 ,m<=500000 )
Output
输出n个数,其中第i个整数表示把与节点i关联的所有边去掉之后(不去掉节点i本身),无向图中有多少个有序点对(x,y),满足x和y不连通。
Sample Input
5 5
1 2
2 3
1 3
3 4
4 5
Sample Output
8
8
16
14
8
限制与约定
时间限制:1s
空间限制:128MB
std:
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#define LL long long
using namespace std;
const int maxn=1e5+;
const int maxm=5e5+;
inline int read()
{
int a=;bool b=;char x=getchar();
while(x<''||''<x){
if(x=='-')b=;
x=getchar();
}
while(''<=x&&x<=''){
a=(a<<)+(a<<)+x-'';
x=getchar();
}
return b?a:-a;
}
int first[maxn],next[maxm*],to[maxm*],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],root,Time;
LL ans[maxn],size[maxn];
int n,m;
void tarjan(int u){
pre[u]=low[u]=++Time;
size[u]=; int temp=;
long long cnt=n-;
for(int i=first[u];i;i=next[i]){
int v=to[i];
if(pre[v]){
low[u]=min(low[u],pre[v]);
}
else{
tarjan(v);
low[u]=min(low[u],low[v]);
size[u]+=size[v]; if(pre[u]<=low[v]){
temp++;
if(u!=root || temp>){
ans[u]+=size[v]*(n-size[v]-);
cnt-=size[v];
}
}
}
}
ans[u]+=cnt*(n-cnt-);
}
int main()
{
n=read();m=read();
const LL N=n+n-;
for(int i=,x,y;i<=m;i++){
x=read();y=read();
add(x,y);add(y,x);
}
for(int i=;i<=n;i++){
if(pre[i])continue;
root=i;
tarjan(i);
}
for(int i=;i<=n;i++){
printf("%lld\n",ans[i]+N);
}
return ;
}
奇葩问题汇总{
1.数据范围为>maxint,故要开long long
2.其中不影响结果的变量cnt如果开int也会影响结果,
因为每一步都要考虑强制转换的问题!!!特别要注意,否则会傻逼!!!
3.因为是双向点对,所以不用复杂的记录当前已经分理出多少点->res[u]
直接乘就行还会变快,!!!而且类似的求单向点对也可以求完双向再/2即可,
排列组合很重要!!!
}