[POI2008]BLO-Blockade（割頂）
摘要：
題目連結：https://www.luogu.org/problemnew/show/P3469
題目大意：給定一張無向圖，求每個點被封鎖之後有多少個有序點對(x,y)(x!=y,1<=x,y<=n)滿足x無法到達y。
思路：根據推樣例得知，若此點非割點，即...
題目連結：ofollow,noindex" target="_blank">https://www.luogu.org/problemnew/show/P3469
題目大意：給定一張無向圖，求每個點被封鎖之後有多少個有序點對(x,y)(x!=y,1<=x,y<=n)滿足x無法到達y。
思路：根據推樣例得知，若此點非割點，即不會影響其他點的連線情況，則封鎖此點後影響的有序點對顯然為(n-1)，則答案即為(n-1)*2，對於割點，則封鎖此點後影響的有序點對即為此點刪去此點後，形成2個不聯通的塊，兩組塊的點數之積，答案×2後再加上(n-1)*2。那麼我們只需要在求割點時，記錄每個節點的深度，深度遍歷時累加即可。
程式碼：
#include <cstdio>
#include <cctype>
#include <iostream>
const int MAXN=100050;
const int MAXM=500050;
typedef long long ll;
using namespace std;
int n,m,u,v,num,cnt,head[MAXN],dfn[MAXN],low[MAXN],dep[MAXN];
ll ans[MAXN];
struct node
{
int to,nextt;
}edge[MAXM<<1];
namespace other
{
inline int read()
{
int x=0;bool sign=false;
char alpha=0;
while(!isdigit(alpha)) sign|=alpha=='-',alpha=getchar();
while(isdigit(alpha)) x=(x<<1)+(x<<3)+(alpha^48),alpha=getchar();
return sign?-x:x;
}
inline int get_min(int a,int b)
{
return a<b?a:b;
}
}
namespace Graph
{
inline void addedge(int u,int v)
{
edge[++num].to=v;
edge[num].nextt=head[u];
head[u]=num;
}
}
namespace Main
{
inline void Input()
{
n=other::read();m=other::read();
for(int i=1;i<=m;i++)
{
u=other::read();v=other::read();
Graph::addedge(u,v);
Graph::addedge(v,u);
}
}
inline bool check(int u,int v,int fa,int child)
{
return (u==fa&&child>=2)||(u!=fa&&low[v]>=dfn[u])?true:false;
}
void tarjan(int u,int fa)
{
int child=0,sum=1,sum2=0;
dfn[u]=low[u]=++cnt;
for(int i=head[u];i;i=edge[i].nextt)
{
int to=edge[i].to;
if(!dfn[to])
{
dep[to]=dep[u]+1;
if(u==fa) child++;
tarjan(to,u);
sum+=dep[to];
low[u]=other::get_min(low[u],low[to]);
if(check(u,to,fa,child))
{
sum2+=dep[to];
ans[u]+=(ll)2*dep[to]*(n-sum2-1);
}
}
else low[u]=other::get_min(low[u],dfn[to]);
}
dep[u]=sum;
ans[u]+=2*(n-1);
}
inline void Solve()
{
for(int i=1;i<=n;i++) if(!dfn[i]) tarjan(i,i);
}
inline void Output()
{
for(int i=1;i<=n;i++) cout<<ans[i]<<endl;
}
}
int main()
{
Main::Input();
Main::Solve();
Main::Output();
return 0;
}