洛谷P2783 有机化学之神偶尔会做作弊（水黑题系列）

12 March 2019 | duanyll | Tags: OI 题解 LCA SCC

这个题看上去好像是tarjan缩点后直接LCA判距离，其实也是这样……

但是一般的tarjan求SCC写法过不了，题目也强调了两个碳不成环，因此可以

• 先DFS一遍双向边变单向边
• 或者tarjan里面加一个v!=fa就好

我写的是后一种

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <vector>
#include <iomanip>
using namespace std;

const int MAXN = 10010;
const int MAXM = 50010;
const int INF = 0x3f3f3f3f;

class LFS {
   public:
    LFS() {
        memset(head, -1, sizeof head);
        ecnt = 0;
        n = 0;
    }
    LFS(int N) {
        memset(head, -1, sizeof head);
        ecnt = 0;
        n = N;
    }
    void adde(int from, int to, int w) {
        e[ecnt].to = to;
        e[ecnt].w = w;
        e[ecnt].next = head[from];
        head[from] = ecnt++;
    }
    void addde(int a, int b, int w) {
        adde(a, b, w);
        adde(b, a, w);
    }

   protected:
    struct Edge {
        int to, next, w;
    } e[MAXM * 2];
    int head[MAXN];
    int ecnt;
    int n;

   private:
    virtual void dfs(int u, int fa) {
        for (int i = head[u]; i != -1; i = e[i].next) {
            int v = e[i].to;
            if (v != fa) {
                dfs(v, u);
            }
        }
    }
};

#include <stack>

class SCC_Tarjan : public LFS {
   public:
   	int scccnt;
    int belong[MAXN];
	
	SCC_Tarjan(int n) : LFS(n) {
    	memset(dfn, -1, sizeof dfn);
        memset(low, -1, sizeof low);
        memset(ins, false, sizeof ins);
		memset(belong,0,sizeof belong);
        tim = 1;
        scccnt = 0;
    }
	
    void solve() {
		for(int i = 1;i<=n;i++){
			if(dfn[i] == -1){
				tarjan(i,0);
			}
		}
    }
	
	//缩点，先调用solve
	void createnew(LFS* map){
		for(int i = 1;i<=n;i++){
			for(int j = head[i];j!=-1;j = e[j].next){
				int u = belong[i];
				int v = belong[e[j].to];
				if(u != v){
					map->adde(u,v,e[j].w);
				}
			}
		}
	}

   protected:
    stack<int> s;
    bool ins[MAXN];
    int mina[MAXN];
    int low[MAXN], dfn[MAXN];
    int tim;
    void tarjan(int u,int fa) {
        dfn[u] = low[u] = tim++;
        s.push(u);
        ins[u] = true;
        for (int i = head[u]; i != -1; i = e[i].next) {
            int v = e[i].to;
            if (fa == v){
            	continue;
            }
            if (dfn[v] == -1) {
                tarjan(v,u);
                low[u] = min(low[u], low[v]);
            } else {
                if (ins[v]) {
                    low[u] = min(low[u], dfn[v]);
                }
            }
        }
        if (dfn[u] == low[u]) {
            scccnt++;
            int v = 0;
            while (v != u) {
                v = s.top();
                s.pop();
                ins[v] = false;
                belong[v] = scccnt;
            }
        }
    }
};

class LCA : public LFS{
   public:
   	int dep[MAXN];
    LCA(int n) : LFS(n) {
        memset(dep, -1, sizeof dep);
    }
    void pre(int rt = 1) { dfs(rt, 1, 0); }
    int querylca(int a, int b) {
        if (dep[a] > dep[b]) swap(a, b);
        int h = dep[b] - dep[a];
        for (int i = 20; i >= 0; i--) {
            if(h & (1 << i)) {
				b = f[b][i];
			}
        }
        if (a == b) return a;
        for (int i = 20; i >= 0; i--) {
            if (f[a][i] == f[b][i]) continue;
            a = f[a][i];
            b = f[b][i];
        }
        return f[a][0];
    }

   protected:
    int f[MAXN][22];

   private:
    void dfs(int u, int d, int fa) {
        dep[u] = d;
        f[u][0] = fa;
        for (int i = 1; i < 21; i++) {
            f[u][i] = f[f[u][i - 1]][i - 1];
        }
        for (int i = head[u]; i != -1; i = e[i].next) {
            int v = e[i].to;
            if (dep[v] == -1) {
                dfs(v, d + 1, u);
            }
        }
    }
};

#include <cctype>
#include <cstdio>

inline int read() {
    int X = 0, w = 0;
    char ch = 0;
    while (!isdigit(ch)) {
        w |= ch == '-';
        ch = getchar();
    }
    while (isdigit(ch)) {
        X = (X << 3) + (X << 1) + (ch ^ 48);
        ch = getchar();
    }
    return w ? -X : X;
}

int main(){
	int n = read();
	int m = read();
	SCC_Tarjan *all = new SCC_Tarjan(n);
	for(int i = 1;i<=m;i++){
		int u = read();
		int v = read();
		all->addde(u,v,1);
	}
	all->solve();
	LCA* map = new LCA(all->scccnt);
	all->createnew(map);
	map->pre();
	int tcnt = read();
	for(int i = 1;i<=tcnt;i++){
		int a,b;
		a = all->belong[read()];
		b = all->belong[read()];
		int lca = map->querylca(a,b);
		int ans = map->dep[a] + map->dep[b] - map->dep[lca]*2 + 1;
		char tmp[64] = {0};
		int pos = 0;
		while (ans){
        	tmp[pos++] = (((bool)(ans & 1)) + '0');
        	ans >>= 1;
    	}
    	for(;pos>0;pos--){
    		putchar(tmp[pos-1]);
    	}
    	putchar('\n');
	}	
}

别忘了输出二进制