## 【CodeChef GRAPHCNT】[May Challenge 2015] Counting on a directed graph

### Code

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

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

int n,m;

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 dfs_cnt,dfn[N],idom[N],semi[N],bst[N],ufs[N],sz[N];
public:
inline void AddEdge(int u, int v) {
}
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]]];
}
}
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;
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() {