题目大意：给定一张无向图，，求每个点被封锁之后有多少个有序点对(x,y)(x!=y,1<=x,y<=n)满足x无法到达y
还是看原题面爽。。。
Tarjan求点双，然后TreeDP即可
时间复杂度O(n+m)
#include <vector>#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>#define M 100100using namespace std;int n,m,cnt;long long ans[M];namespace Origin_Graph{struct abcd{int to,next;}table[1001001];int head[M],tot;vector<int> in_DCC[M];int size[M<<1];void Add(int x,int y){table[++tot].to=y;table[tot].next=head[x];head[x]=tot;}void Tarjan(int x){static int dpt[M],low[M],T;static int stack[M],top;int i;dpt[x]=low[x]=++T;stack[++top]=x;for(i=head[x];i;i=table[i].next){if(dpt[table[i].to])low[x]=min(low[x],dpt[table[i].to]);else{Tarjan(table[i].to);low[x]=min(low[x],low[table[i].to]);if(low[table[i].to]==dpt[x]){int t;++cnt;do{t=stack[top–];in_DCC[t].push_back(cnt);size[cnt]++;}while(t!=table[i].to);in_DCC[x].push_back(cnt);size[cnt]++;}}}}}namespace DCC_Graph{struct abcd{int to,next;}table[M<<2];int head[M<<1],tot;int size[M<<1];void Add(int x,int y){table[++tot].to=y;table[tot].next=head[x];head[x]=tot;}void Tree_DP(int x,int from){int i;if(x<=n){for(i=head[x];i;i=table[i].next){if(table[i].to==from)continue;Tree_DP(table[i].to,x);ans[x]+=(long long)size[x]*(size[table[i].to]-1);size[x]+=size[table[i].to]-1;}ans[x]+=(long long)size[x]*(n-size[x]-1);}else{size[x]=Origin_Graph::size[x];for(i=head[x];i;i=table[i].next){if(table[i].to==from)continue;Tree_DP(table[i].to,x);size[x]+=size[table[i].to];}}}}int main(){using namespace Origin_Graph;int i,x,y;cin>>n>>m;cnt=n;if(n==1){cout<<0<<endl;return 0;}for(i=1;i<=m;i++){scanf("%d%d",&x,&y);Add(x,y);Add(y,x);}Tarjan(1);for(i=1;i<=n;i++)if(in_DCC[i].size()>=2){vector<int>::iterator it;for(it=in_DCC[i].begin();it!=in_DCC[i].end();it++){DCC_Graph::Add(i,*it);DCC_Graph::Add(*it,i);}}DCC_Graph::Tree_DP(n+1,0);for(i=1;i<=n;i++)printf("%lld\n",ans[i]+(n-1)<<1);return 0;}
去看日出，去散步，去欣赏大自然，
