HDU3686 Traffic Real Time Query System

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 881 Accepted Submission(s): 151

Problem Description

City C is really a nightmare of all drivers for its traffic jams. To solve the traffic problem, the mayor plans to build a RTQS (Real Time Query System) to monitor all traffic situations. City C is made up of N crossings and M roads, and each road connects two crossings. All roads are bidirectional. One of the important tasks of RTQS is to answer some queries about route-choice problem. Specifically, the task is to find the crossings which a driver MUST pass when he is driving from one given road to another given road.

Input

There are multiple test cases.
For each test case:
The first line contains two integers N and M, representing the number of the crossings and roads.
The next M lines describe the roads. In those M lines, the ith line (i starts from 1)contains two integers Xi and Yi, representing that roadi connects crossing Xi and Yi (Xi≠Yi).
The following line contains a single integer Q, representing the number of RTQs.
Then Q lines follows, each describing a RTQ by two integers S and T(S≠T) meaning that a driver is now driving on the roads and he wants to reach roadt . It will be always at least one way from roads to roadt.
The input ends with a line of “0 0”.
Please note that: 0<N<=10000, 0<M<=100000, 0<Q<=10000, 0<Xi,Yi<=N, 0<S,T<=M

Output

For each RTQ prints a line containing a single integer representing the number of crossings which the driver MUST pass.

Sample Input

5 6

1 2

1 3

2 3

3 4

4 5

3 5

2 3

2 4

0 0

Sample Output

**********************************************************

题目大意：一个城市有n个路口，m条无向公路。现在要求从第S条路到第T条路必须经过的点有几个。

解题思路：tarjan求点的双连通分量，然后缩点，然后LCA。

wa了良久，竟然因为：

1.题目要求的是从一条路到另一条路的必经点，不是从一个点到另一个点的必经点

2.这题虽说保证从roadS到roadT一定有路，但没说这个图是连通图，也就是缩点之后有多个树，不是只有一颗树

注意了上面两点就能AC。苦于因为从wa的代码改过来AC的，代码已经非常搓了。。。。

#include <map>
#include <stack>
#include <queue>
#include <math.h>
#include <vector>
#include <string>
#include <fstream>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <iostream>
#include <algorithm>
#define N 200005
#define M 100005
#define E
#define inf 0x3f3f3f3f
#define eps 1e-8
#define LL long long
#define clr(a,b) memset(a,b,sizeof(a))
#define D(a) ((a)*(a))
using namespace std;

struct Node
{
    int a,id;
    Node(int t1,int t2):a(t1),id(t2){}
};
int x[M],y[M],eid[M],me[M];
int n,m,q,qu[N][2],gp[N],sum[N];
int num[N],ans[N],vis[N],fa[N],gk[N];
vector<int>gra[N],tre[N];
vector<Node>lca[N];
int dfn[N],low[N],now,gid;
stack<int>sta;
stack<Node>ste;

int findfa(int s)
{
    while(s!=fa[s])s=fa[s];
    return s;
}

void tarjan(int s,int p)
{
    dfn[s]=low[s]=++now;
    int flag=0;
    sta.push(s);
    for(int i=0;i<gra[s].size();i++)
    {
        int e=gra[s][i];
        if(me[e])continue;
        me[e]=1;
        int t=x[e];if(t==s)t=y[e];
        ste.push(Node(e,t));
        if(!dfn[t])
        {
            gk[t]=e;
            tarjan(t,s);
            low[s]=min(low[s],low[t]);
            if(low[t]>=dfn[s])
            {
                if(flag==0)
                {
                    num[++gid]=s;
                    flag=gp[s]=gid;
                }
                ++gid;
                tre[gp[s]].push_back(gid);
                tre[gid].push_back(gp[s]);
                while(!sta.empty())
                {
                    int k=sta.top();
                    sta.pop();
                    if(gp[k])
                    {
                        int a=gp[k];
                        tre[a].push_back(gid);
                        tre[gid].push_back(a);
                    }
                    else gp[k]=gid;
                    if(k==t)break;
                }
                while(!ste.empty())
                {
                    int ee=ste.top().a,hh=ste.top().id;
                    ste.pop();
                    eid[ee]=gid;
                    if(ee==gk[t])break;
                }
            }
        }
        low[s]=min(dfn[t],low[s]);
    }
}

void LCA(int p,int s,int pre)
{
    sum[p]=s;
    if(num[p])s++;
    for(int i=0;i<tre[p].size();i++)
    {
        int t=tre[p][i];
        if(t!=pre)
        {
            LCA(t,s,p);
            fa[findfa(t)]=p;
        }
    }
    vis[p]=1;
    for(int i=0;i<lca[p].size();i++)
    {
        int t=lca[p][i].a,id=lca[p][i].id;
        if(vis[t])
        {
            int f=fa[findfa(t)];
            ans[id]=sum[p]+sum[t]-2*sum[f];
            if(num[f])ans[id]--;
        }
    }
}

void re(void)
{
	for(int i=1;i<=n;i++)
        gra[i].clear();
    for(int i=1;i<=m;i++)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        x[i]=a;y[i]=b;eid[i]=0;me[i]=0;
        gra[a].push_back(i);
        gra[b].push_back(i);
    }
    scanf("%d",&q);
    for(int i=1;i<=q;i++)
        scanf("%d%d",&qu[i][0],&qu[i][1]);
}

void run(void)
{
	for(int i=1;i<=n;i++)
	{
	    dfn[i]=num[i]=gp[i]=gk[i]=0;
	    tre[i].clear();
	}
    now=gid=0;
    for(int i=1;i<=n;i++)
        if(!dfn[i])
        {
            while(!sta.empty())sta.pop();
            while(!ste.empty())ste.pop();
            tarjan(i,0);
        }
    for(int i=1;i<=gid;i++)
    {
        lca[i].clear();
        vis[i]=sum[i]=0;
        fa[i]=i;
    }
    for(int i=1;i<=q;i++)
    {
        int a=eid[qu[i][0]],b=eid[qu[i][1]];
        if(a==b)
        {
            ans[i]=0;
            continue;
        }
        lca[a].push_back(Node(b,i));
        lca[b].push_back(Node(a,i));
    }
    for(int i=1;i<=n;i++)
        if(!vis[gp[i]])
            LCA(gp[i],0,-1);
    for(int i=1;i<=q;i++)
        printf("%d\n",ans[i]);
}

int main()
{
    while(scanf("%d%d",&n,&m),n+m)
	{
		re();
		run();
	}
	return 0;
}