Tag: 支配树

相关链接

题目传送门：https://www.codechef.com/problems/GRAPHCNT
数据生成器：http://paste.ubuntu.com/24319212/
神犇题解Ⅰ：http://blog.csdn.net/a710128/article/details/49913553
神犇题解Ⅱ：http://www.cnblogs.com/meowww/p/6475952.html

解题报告

就是支配树的板题？

我们可以用Lengauer Tarjan算法在$O(n \alpha (n))$的时间复杂度内解决这个问题
也可以求出所有的半支配点，然后用灭绝树来搞，时间复杂度：$O(n \log n)$
另外之前我还看到一种非常鬼畜地LCT+灭绝树地做法，时间复杂度跑起来像：$O(n \log n)$

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 100009;
const int M = 1500009;

int n,m;

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

class Dominator_Tree{
	int dom[N],pre[N],head[N],nxt[M],to[M],que[N],anc[N];
	int dfs_cnt,dfn[N],idom[N],semi[N],bst[N],ufs[N],sz[N];
	public: 
		inline void AddEdge(int u, int v) {
			AddEdge(head, u, v);
			AddEdge(pre, v, u);	
		}
		inline void build() {
			DFS(1);
			for (int i=dfs_cnt,w;w=que[i],i>1;i--) {
				for (int j=pre[w];j;j=nxt[j]) {
					if (dfn[to[j]]) {
						update(to[j]);
						if (dfn[semi[bst[to[j]]]] < dfn[semi[w]])
							semi[w] = semi[bst[to[j]]];
					}
				}
				AddEdge(dom, semi[w], w);
				ufs[w] = anc[w]; w = que[i-1];
				for (int j=dom[w];j;j=nxt[j]) {
					update(to[j]);
					if (semi[bst[to[j]]] == w) idom[to[j]] = w;
					else idom[to[j]] = bst[to[j]];
				}
			}
			for (int i=2,w;w=que[i],i<=dfs_cnt;i++)
				idom[w] = ((idom[w] == semi[w])? idom[w]: idom[idom[w]]);
		}
		inline LL solve() {
			LL ret = dfs_cnt * (dfs_cnt - 1ll) / 2ll; 
			for (int i=dfs_cnt,w;w=que[i],i>1;i--) { 
				if (++sz[w], idom[w] != 1) sz[idom[w]] += sz[w];
				else ret -= (sz[w] - 1ll) * sz[w] / 2ll;
			} return ret;
		}
	private:
		inline void AddEdge(int *arr, int u, int v) {
			static int E = 1; 
			to[++E] = v; nxt[E] = arr[u]; arr[u] = E;
		}	
		void DFS(int w) {
			dfn[w] = ++dfs_cnt; que[dfs_cnt] = w;
			bst[w] = semi[w] = ufs[w] = w;
			for (int i=head[w];i;i=nxt[i]) 
				if (!dfn[to[i]]) anc[to[i]] = w, DFS(to[i]);
		}
		int update(int w) {
			if (ufs[w] == w) return w;
			int tmp = update(ufs[w]);
			if (dfn[semi[bst[ufs[w]]]] < dfn[semi[bst[w]]])
				bst[w] = bst[ufs[w]];
			return ufs[w] = tmp;
		}
}DMT;

int main() {
	n = read(); m = read();
	for (int i=1,u,v;i<=m;i++) {
		u = read(); v = read();
		DMT.AddEdge(u, v);
	}
	DMT.build();
	cout<<DMT.solve();
	return 0;
}