[POI2008]BLO-Blockade，洛谷之提高历练地，强连通分量

正题

      [POI2008]BLO-Blockade

      这一题很神奇啊~

      我们来想想两个点不能连通和强连通有什么关系。

      那么其实很明显，如果当前点所遍历到的子节点不能遍历到祖先节点，那么说明子节点只能通过该点来去到祖先节点，这样产生的有序点对数量就是son[x]*(n-son[x]-1)*2，（假设当前点为x，则儿子节点即为son[x]）

      所以可以延伸出来一个概念——割点，割点即为去掉该点后，原图被分为更多的连通块。

      所以我们判断该儿子是否只能通过该点到达祖先节点，是的话那就要加上答案，否则就不用理。

      具体看下代码，不懂怎么判割点的建议去学一学

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<stack>
#include<iostream>
using namespace std;

int m;
long long n;
struct edge{
	int y,next,x;
}s[1000010];
struct node{
	int dfn,low;
}op[100010];
long long ans[100010];
int first[100010];
long long size[100010];
int len=0;
int now=0;

void ins(int x,int y){
	len++;
	s[len].y=y;s[len].next=first[x];first[x]=len;
}

void Tarjan(int x){
	op[x].low=op[x].dfn=++now;
	size[x]=1;
	long long t=0;
	for(int i=first[x];i!=0;i=s[i].next){
		int y=s[i].y;
		if(op[y].dfn==0){//如果y没有被遍历过
			Tarjan(y);//往下搜
			size[x]+=size[y];//size[x]表示x的子树大小
			if(op[y].low<op[x].low) op[x].low=op[y].low;//用儿子节点的low来更新自己的low
			if(op[x].dfn<=op[y].low){//没错，op[x].dfn<=op[y].low表示y不能通过其他路径遍历到祖先以及其他非该子树节点，即x是割点
				ans[x]+=t*size[y];//t表示前面的点,用t乘上size[y]意思就是y所在子树的每一个点不能到前面的t个点。
				t+=size[y];//更新t
			}
		}
		else if(op[y].dfn<op[x].low) op[x].low=op[y].dfn;//更新low
	}
	ans[x]+=t*(n-t-1);//该子树的点不能到达祖先
}

int main(){
	scanf("%lld %d",&n,&m);
	for(int i=1;i<=m;i++){
		int x,y;
		scanf("%d %d",&x,&y);
		ins(x,y),ins(y,x);//无向图建边
	}
	for(int i=1;i<=n;i++)
		if(op[i].dfn==0) Tarjan(i);//跑Tarjan算答案
	for(int i=1;i<=n;i++)
		printf("%lld\n",(ans[i]+n-1)<<1);//输出，记得加上(n-1)*2,因为这个点不能去到其他的n-1个点，乘二是因为双向点对
}