UVALive 4839 HDU 3686 Traffic Real Time Query System

題意：給出一幅圖，詢問從一條邊到另一條有幾個點必被經過

沒看題解思路完全不對。。似乎知道了tarjan的新姿勢

思路：首先按邊跑tarjan。然後記錄一下每條邊在哪一個塊中，記錄一下割點；

然後建圖：對于每個割點所在的塊中（每個割點肯定在多個塊中），建一個新點跟它們連邊；

然後就是一棵樹啦，當然到樹剖啦。然後詢問就是統計一條鍊上的割點有多少啦

（縮點基本是抄襲）

代碼：

#include <bits/stdc++.h>
#define N 20009
#define M 200009
using namespace std;
int first[N],number,x,y,n,m,dfn[N],low[N],sta[M];
int ebelong[M],subnet[N],iscut[N],Number,First[N<<1];
int top,cnt,taj,treecut[N<<1],vis[N<<1],Q,size[N<<1];
int num[N<<1],deep[N<<1],Top[N<<1],father[N<<1],Mson[N<<1];
vector<int> q[N];
struct edge
{
	int from,to,next,val,vis;
	void add(int x,int y,int z)
	{
		from=x,to=y,next=first[x],first[x]=number,val=z,vis=0;
	}
}e[M<<1];
struct Edge
{
	int to,next;
	void add(int x,int y)
	{
		to=y,next=First[x],First[x]=Number;
	}
}E[N<<3];
void tarjan(int x)
{
	dfn[x]=low[x]=++cnt;
	for (int i=first[x];i;i=e[i].next)
		if (!e[i].vis)
		{
			e[i].vis=e[i^1].vis=1;
			sta[++top]=i;
			if (!dfn[e[i].to])
			{
				tarjan(e[i].to);
				low[x]=min(low[x],low[e[i].to]);
				if (low[e[i].to]>=dfn[x])
				{
					++taj;
					subnet[x]++;
					iscut[x]=1;
					int y,j;
					do
					{
						j=sta[top--];
						q[e[j].from].push_back(taj);
						q[e[j].to].push_back(taj);
						ebelong[e[j].val]=taj;
						y=e[j].from;
					}while (y!=x);
				}
			}
			else low[x]=min(low[x],low[e[i].to]);
		}
}
void dfs(int x)
{
	vis[x]=1;
	for (int i=First[x];i;i=E[i].next)
		if (!vis[E[i].to])
		{
			num[E[i].to]=num[x];
			if (treecut[x]) num[E[i].to]++;
			dfs(E[i].to);
		}
}
void dfs1(int x)
{
	size[x]=1;
	deep[x]=deep[father[x]]+1;
	for (int i=First[x];i;i=E[i].next)
		if (E[i].to!=father[x])
		{
			father[E[i].to]=x;
			dfs1(E[i].to);
			size[x]+=size[E[i].to];
			if (size[E[i].to]>size[Mson[x]]) Mson[x]=E[i].to;
		}
}
void dfs2(int x,int y)
{
	Top[x]=y;
	if (Mson[x]) dfs2(Mson[x],y);
	for (int i=First[x];i;i=E[i].next)
		if (E[i].to!=father[x]&&E[i].to!=Mson[x])
			dfs2(E[i].to,E[i].to);
}
int lca(int x,int y)
{
	for (;Top[x]!=Top[y];x=father[Top[x]])
		if (deep[Top[x]]<deep[Top[y]]) swap(x,y);
	return deep[x]<deep[y]?x:y;
}
int main()
{
	while (scanf("%d%d",&n,&m),n&&m)
	{
		for (int i=1;i<=n;i++)
			first[i]=dfn[i]=low[i]=iscut[i]=subnet[i]=0;
		for (int i=1;i<=n;i++) q[i].clear();
		number=1,top=cnt=taj=Number=0;
		for (int i=1;i<=m;i++)
		{
			scanf("%d%d",&x,&y);
			ebelong[i]=0;
			e[++number].add(x,y,i);
			e[++number].add(y,x,i);
		}
		for (int i=1;i<=n;i++)
			if (!dfn[i])
			{
				tarjan(i);
				subnet[i]--;
				if (subnet[i]<=0) iscut[i]=0;
			}
		for (int i=1;i<=taj+n;i++) First[i]=treecut[i]=0;
		for (int i=1;i<=n;i++)
			if (iscut[i])
			{
				sort(q[i].begin(),q[i].end());
				treecut[++taj]=1;
				E[++Number].add(taj,q[i][0]);
				E[++Number].add(q[i][0],taj);
				for (int j=1;j<q[i].size();j++)
					if (q[i][j-1]!=q[i][j])
					{
						E[++Number].add(taj,q[i][j]);
						E[++Number].add(q[i][j],taj);
					}
			}
		for (int i=1;i<=taj;i++)
			Mson[i]=deep[i]=num[i]=father[i]=Top[i]=vis[i]=size[i]=0;
		for (int i=1;i<=taj;i++)
			if (!vis[i]) dfs(i),dfs1(i),dfs2(i,i);
		scanf("%d",&Q);
		for (int i=1;i<=Q;i++)
		{
			scanf("%d%d",&x,&y);
			x=ebelong[x],y=ebelong[y];
			if (!x||!y) puts("0");
			else
			{
				int z=lca(x,y);
				printf("%d\n",num[x]+num[y]-2*num[z]-treecut[z]);
			}
		}
	}
	return 0;
}