P2783 有机化学之神偶尔会作弊

Skyzhou666 · 2022-10-26 16:53:10 · 算法·理论

水黑题怎么变成紫题后还这么水（

怎么变蓝了（

学完了Tarjan之后，想多练几道题，看到模板题怎么都是绿题，突然发现这有个紫题怎么看都像是无向图边双连通分量Tarjan缩点模板，于是心血来潮

怎么大家都在用LCA啊我不会啊（

但这道题数据水到缩完点直接搜索就能过

#include <iostream>
#include <vector>
#include <stack>
#include <cstring>
#define MAXN 10001
using namespace std;

int n, m, dfn[MAXN], low[MAXN], coli, col[MAXN], cnt, d[MAXN];
bool vis[MAXN];
stack <int> st;
vector <int> g[MAXN], ng[MAXN];

void Tarjan(int u, int lst)
{
    dfn[u] = low[u] = ++cnt;
    vis[u] = true;
    st.push(u);
    for(int x = 0; x < g[u].size(); x++)
    {
        int v = g[u][x];
        if(v == lst) continue; //只需要加这一行就变成了无向图缩点
        if(!dfn[v])
        {
            Tarjan(v, u);
            low[u] = min(low[u], low[v]);
        }
        else if(vis[v]) low[u] = min(low[u], dfn[v]);
    }
    if(dfn[u] == low[u])
    {
        coli++;
        int v;
        do
        {
            v = st.top(); st.pop();
            vis[v] = false;
            col[v] = coli;
        } while(v != u);
    }
}

void er(int i)
{
    vector <int> ans;
    while(i)
    {
        ans.push_back(i % 2);
        i >>= 1;
    }
    for(int x = ans.size()-1; x >= 0; x--) cout << ans[x];
    cout << endl;
}

void dfs(int u)
{
    for(int x = 0; x < ng[u].size(); x++)
    {
        int v = ng[u][x];
        if(!d[v])
        {
            d[v] = d[u] + 1;
            dfs(v);
        }
    }
}

int findAns(int i, int j)
{
    memset(d, 0, sizeof(d));
    d[i] = 1;
    dfs(i);
    return d[j];
}

int main()
{
    int tot;
    cin >> n >> m;
    for(int x = 0; x < m; x++)
    {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    for(int x = 1; x <= n; x++)
        if(!dfn[x]) Tarjan(x, 0);
    for(int x = 1; x <= n; x++)
    {
        for(int y = 0; y < g[x].size(); y++)
        {
            int v = g[x][y];
            if(col[x] != col[v])
            {
                ng[col[x]].push_back(col[v]);
                ng[col[v]].push_back(col[x]);
            }
        }
    }
    cin >> tot;
    while(tot--)
    {
        int u, v;
        cin >> u >> v;
        er(findAns(col[u], col[v]));
    }
    return 0;
}