救救蒟蒻吧QAQ
by NaCly_Fish @ 2018-11-19 23:02:33
orzorz萌新切黑题
by Mr_Wu @ 2018-11-19 23:04:20
@[Mr_Wu](/space/show?uid=62308) 呜哇
by NaCly_Fish @ 2018-11-19 23:08:08
我要去碎觉觉了
给您看看蒟蒻我的
```cpp
#include <bits/stdc++.h>
#define MAXN 10005
using namespace std;
namespace Tarjan
{
vector < int > e[MAXN*10];
vector < int > ed[MAXN*10];
int belong [MAXN];
int flcnt = 0;
int size[MAXN];
int dfn [MAXN], low[MAXN];
int n, m;
int cnt = 1;
stack < int > s;
bool used[MAXN];
void tarjan (int u, int f)
{
dfn[u] = low[u] = cnt++;
s.push(u);
int v = 0;
used[u] = 1;
for (int i = 0; i < e[u].size(); i ++)
{
if ((v=e[u][i]) != f)
if (!dfn[v]) tarjan(v, u), low[u] = min (low[u], low[v]);
else if (used[v]) low[u] = min(low[u], dfn[v]);
}
if (low[u] == dfn[u])
{
flcnt++;
while (v != u)
{
v = s.top();
s.pop(), used[v] = 0, size[flcnt]++, belong[v] = flcnt;
}
}
return ;
}
void build ()
{
for (int i = 1; i <= n; i ++)
for (int j = 0; j < e[i].size(); j ++)
{
register int x = belong[i], y = belong[e[i][j]];
if (x != y) ed[x].push_back (y);
}
return ;
}
}
using namespace Tarjan;
namespace LCA
{
int q;
int deep[MAXN], T[MAXN][25];
void dfs (int u, int f)
{
deep[u] = deep[f]+1;
T[u][0] = f;
for (register int i = 0; i < ed[u].size(); i ++)
if (ed[u][i] != f)
dfs (ed[u][i], u);
return ;
}
int Lca(int u, int v)
{
if (deep[u] < deep[v]) swap (u, v);
int d = deep[u] - deep[v];
for (register int i = 20; i >= 0; i --)
if (d & (1<<i))
u = T[u][i];
if(u == v)return u;
for (register int i = 20; i >= 0; i --)
if (T[u][i] != T[v][i])
u = T[u][i], v = T[v][i];
return T[u][0];
}
}
using namespace LCA;
namespace OUTPUT
{
int tmp[64];
void print(int res)
{
if(res==0) { puts("0"); return ;}
if(res<0) { putchar('-');res=0-res; }
while(res) tmp[++tmp[0]]=res&1,res>>=1;
while(*tmp) putchar(tmp[(*tmp)--]+'0');
putchar('\n');
}
}
using namespace OUTPUT;
int main ()
{
scanf ("%d%d", &n, &m);
while(m --)
{
register int a, b;
scanf ("%d%d", &a, &b);
e[a].push_back(b), e[b].push_back(a);
}
for (int i = 1; i <= n; i ++)
if (!dfn[i])
tarjan (i, 0);
build ();
dfs (1, -1);
for (int i = 1; i <= 20; i ++)
for (int j = 1; j <= flcnt; j ++)
T[j][i] = T[T[j][i-1]][i-1];
scanf("%d", &q);
while (q --)
{
int a, b;
scanf ("%d%d", &a, &b);
int lca = Lca(belong[a], belong[b]);
print(deep[belong[a]] + deep[belong[b]]-(deep[lca]<<1)+1);
}
return 0;
}
```
by tocek_shiki @ 2018-11-19 23:14:22
@[寒炽·刻刻帝](/space/show?uid=49562) 不要只丢下代码就跑啊
by NaCly_Fish @ 2018-11-19 23:15:10
@[NaCly_Fish](/space/show?uid=115864) 我爸爸在催我了qwq，没来及看完，抱歉了
~~参数要靠自己啊~~
by tocek_shiki @ 2018-11-19 23:16:35
刚学tarjan的蒟蒻路过qwq
by qsmoonzh @ 2018-11-19 23:22:54
不会tarjan的萌新路过qwq
by かなで @ 2018-11-20 05:58:46
%神鱼qwq
by zrzluck99 @ 2019-06-19 13:43:19
%神鱼qwq
by 明依 @ 2019-08-25 16:11:24