最短路

题目：给一个连通图，每次询问两点间最短路。每条边的长度都是1。

思路：看数据范围我们就知道普通的最短路是无法在规定的时间爬完的，所以我们盯上了长度为1，和m<n+100。如果是一颗树，我们可以用Lca求最短路，每一次查询为O(log(n))。我们已知这是一个连通图，所以我们可以用并查集生成最小生成树，多余的边我们先保存。在做完Lca的预处理后将多余的边加入，对每一条多余的边的一个端点进行求取该点到每一个点的距离，可以用求最短路的算法求取。最后我们求二个点的最短路时可以用树上的距离与这二个点到每一个求了最短路的点的距离和中取最小值。
我的代码水平有点低，交了几次才卡过去。

代码：

#include <bits/stdc++.h>
#define inf 1000000007
using namespace std;

typedef long long ll;

vector<int> g[100005];
int n, m, ran[100005], pre[100005], ji=0;
int di[105][100005], flag[100005], jj=0;

int read()
{
    int x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9') {if(c=='-') f=-1;c=getchar();}
    while(c>='0'&&c<='9') x=(x<<1)+(x<<3)+c-'0',c=getchar();
    return f*x;
}

void inti()
{
    for(int i=0; i<=n; i++)
    {
        pre[i]=i;
        ran[i]=0;
    }
}

int find(int x)
{
    if(pre[x]==x)
    {
        return x;
    }
    return pre[x]=find(pre[x]);
}

void unite(int x,int y)
{
    x=find(x);
    y=find(y);
    if(x!=y)
    {
        if(ran[x]<ran[y])
        {
            pre[x]=y;
        }
        else
        {
            if(ran[x]==ran[y])
            {
                ran[x]++;
            }
            pre[y]=x;
        }
    }
}

bool same(int x,int y)
{
    return find(x)==find(y);
}

struct edge
{
    int u, v;
}edge[105];

struct w
{
    int u, v;
}w[100005];
int parent[21][100005];
int dep[100005];

void dfs(int v,int p,int d)
{
    parent[0][v]=p;
    dep[v]=d;
    for(int i=0; i<g[v].size(); i++)
    {
        if(g[v][i]!=p)
        {
            dfs(g[v][i],v,d+1);
        }
    }
}

int lca(int u,int v)
{
    if(dep[u]>dep[v])
    {
        swap(u,v);
    }
    for(int k=0; (1<<k)<n; k++)
    {
        if((dep[v]-dep[u]>>k)&1)
        {
            v=parent[k][v];
        }
    }
    if(u==v)
    {
        return u;
    }
    for(int k=20; k>=0; k--)
    {
        if(parent[k][v]!=parent[k][u])
        {
            v=parent[k][v];
            u=parent[k][u];
        }
    }
    return parent[0][u];
}

int use[100005];

void dij(int v,int jj)
{
    fill(di[jj],di[jj]+100005,inf);
    memset(use,0,sizeof(use));
    di[jj][v]=0;
    queue<int> q;
    q.push(v);
    while(!q.empty())
    {
        int vi=q.front();
        q.pop();
        if(use[vi]==0)
        {
            for(int i=0; i<g[vi].size(); i++)
            {
                if(di[jj][g[vi][i]]>di[jj][vi]+1)
                {
                    di[jj][g[vi][i]]=di[jj][vi]+1;
                    q.push(g[vi][i]);
                }
            }
            use[vi]=1;
        }
    }
}

int main()
{
    n=read();
    m=read();
    inti();
    for(int i=0; i<m; i++)
    {
        int u, v;
        u=read();
        v=read();
        if(same(u,v))
        {
            edge[ji].u=u;
            edge[ji++].v=v;
        }
        else
        {
            unite(u,v);
            g[u].push_back(v);
            g[v].push_back(u);
        }
    }
    dfs(1,-1,0);
    for(int k=0; (1<<(k+1))<n; k++)
    {
        for(int i=1; i<=n; i++)
        {
            if(parent[k][i]<0)
            {
                parent[k+1][i]=-1;
            }
            else
            {
                parent[k+1][i]=parent[k][parent[k][i]];
            }
        }
    }
    int q;
    q=read();
    for(int i=0; i<ji; i++)
    {
        g[edge[i].u].push_back(edge[i].v);
        g[edge[i].v].push_back(edge[i].u);
    }
    for(int i=0; i<ji; i++)
    {
        if(flag[edge[i].u]==0)
        {
            flag[edge[i].u]=1;
            dij(edge[i].u,jj);
            jj++;
        }
        flag[edge[i].v]=1;
    }
    while(q--)
    {
        int x, y;
        x=read();
        y=read();
        int p=lca(x,y);
        int z=dep[x]+dep[y]-2*dep[p];
        for(int i=0; i<jj; i++)
        {
            z=min(z,di[i][x]+di[i][y]);
        }
        printf("%d\n",z);
    }
    return 0;
}