BZOJ 1123 POI2008 BLO Tarjan+树形DP

题目大意：给定一张无向图，求每个点被封锁之后有多少个有序点对(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 100100
using 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;
}

BZOJ 1123 POI2008 BLO Tarjan+树形DP

原文：http://blog.csdn.net/popoqqq/article/details/44619667