uva(Transitive Closure)

source: http://livearchive.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=388&problem=3063&mosmsg=Submission+received+with+ID+928527

title:Transitive Closure

题目简述：给出一个有向图，求有多少组(x, y)使得x到y有一条路径并且x不等于y。

解法： 强连通分量+拓扑排序+位运算#include <stdio.h>

#include <vector>
using namespace std;
/************************
init: stop，cnt，scnt, en置0； pre[]置-1, fir[]置NULL
CALL：for(i = 0; i < n; i++) if(-1 == pre[i]) tarjan(i, n);
************************/
#define V 2505
#define E 10005
typedef vector<int> vi;
const int K=V/30+5;
struct e{
	int v;
	e* nxt;
}es[E];
e* fir[V];
int id[V], pre[V], low[V], s[V], stop, cnt, scnt;
int en;
int n;
int num[V], size[V], tid[V];
vi son[V], rson[V];
int has[V][K];

void tarjan(int v, int n){
	int t, minc = low[v] = pre[v] = cnt++;
	e* cur;
	s[stop++] = v;
	for(cur = fir[v]; cur ; cur = cur->nxt){
		if(-1 == pre[cur->v]) tarjan(cur->v, n);
		if(low[cur->v] < minc) minc = low[cur->v];
	}
	if(minc < low[v]){
		low[v] = minc;
		return;
	}
	do{
		id[t = s[--stop]] = scnt; low[t] = n;
	}while(t != v);
	++scnt;   //强连通分量的个数
}
inline void add_e(int u, int v){
	es[en].v = v; es[en].nxt = fir[u]; fir[u] = &es[en++];
}
void getSCC(int n){  //get strongly connected component
	stop = cnt = scnt = 0;
	int i;
	for(i = 0; i < n; i++) pre[i] = -1;
	for(i = 0; i < n; i++) if(-1 == pre[i]) tarjan(i, n);
}

bool input(){
	scanf("%d", &n);
	int u, v, i, e;
	scanf("%d", &e);
	for(i = 0; i < n; i++) fir[i] = NULL;
	en = 0;
	while(e--){
		scanf("%d%d", &u, &v);
		u--; v--;
		add_e(u, v);
	}
	return true;
}
void topu(int id){
	pre[id]=0;
	int v, i, s;
	for(s=son[id].size(), i=0; i<s; i++){
		if(pre[v=son[id][i]]==-1){
			topu(v);
		}
	}
	tid[cnt++]=id;
}
void solve(){
	getSCC(n);
	int i, ans, u, v, k, j, s, h, g;
	e* cur;
	for(i=0; i<scnt; i++){
		son[i].clear();
		rson[i].clear();
		size[i]=0;
	}
	for(i=0; i<n; i++){
		size[u=id[i]]++;
		for(cur=fir[i]; cur; cur=cur->nxt){
			if((v=id[cur->v])!=u){
				son[u].push_back(v);
				rson[v].push_back(u);
			}
		}
	}
	for(ans=i=0; i<scnt; i++){
		ans += size[i]*(size[i]-1);
		pre[i]=-1;
	}
	cnt=0;
	k=scnt/30+(scnt%30==0 ? 0: 1);
	for(i=0; i<scnt; i++){
		if(pre[i]==-1){
			topu(i);
		}
		for(j=0; j<k; j++){
			has[i][j]=0;
		}
	}
	for(i=0; i<scnt; i++){
		u=tid[i];
		for(s=son[u].size(), j=0; j<s; j++){
			v=son[u][j];
			for(h=0; h<k; h++){
				has[u][h] |= has[v][h];
			}
			has[u][v/30] |= (1<<(v%30));
		}
		for(h=0; h<k; h++){
			v=has[u][h];
			for(g=0; v; v>>=1, g++){
				if(v&1){
					ans += size[u]*size[h*30+g];
				}
			}
		}
	}
	printf("%d\n", ans);
}
int main(){
	int t;
	scanf("%d", &t);
	while(t--){
		input();
		solve();
	}
	return 0;
}

暴力广搜的版本：

#include <stdio.h>
#include <vector>
using namespace std;
/************************
init: stop，cnt，scnt, en置0； pre[]置-1, fir[]置NULL
CALL：for(i = 0; i < n; i++) if(-1 == pre[i]) tarjan(i, n);
************************/
#define V 2505
#define E 10005
typedef vector<int> vi;
const int K=V/30+5;
struct e{
	int v;
	e* nxt;
}es[E];
e* fir[V];
int id[V], pre[V], low[V], s[V], stop, cnt, scnt;
int en;
int n;
int num[V], size[V], tid[V], que[V];
vi son[V];
int has[V][K];

void tarjan(int v, int n){
	int t, minc = low[v] = pre[v] = cnt++;
	e* cur;
	s[stop++] = v;
	for(cur = fir[v]; cur ; cur = cur->nxt){
		if(-1 == pre[cur->v]) tarjan(cur->v, n);
		if(low[cur->v] < minc) minc = low[cur->v];
	}
	if(minc < low[v]){
		low[v] = minc;
		return;
	}
	do{
		id[t = s[--stop]] = scnt; low[t] = n;
	}while(t != v);
	++scnt;   //强连通分量的个数
}
inline void add_e(int u, int v){
	es[en].v = v; es[en].nxt = fir[u]; fir[u] = &es[en++];
}
void getSCC(int n){  //get strongly connected component
	stop = cnt = scnt = 0;
	int i;
	for(i = 0; i < n; i++) pre[i] = -1;
	for(i = 0; i < n; i++) if(-1 == pre[i]) tarjan(i, n);
}

bool input(){
	scanf("%d", &n);
	int u, v, i, e;
	scanf("%d", &e);
	for(i = 0; i < n; i++) fir[i] = NULL;
	en = 0;
	while(e--){
		scanf("%d%d", &u, &v);
		u--; v--;
		add_e(u, v);
	}
	return true;
}
int BFS(int s){
	int l, r, num, i, v, u, ans;
	pre[s]=s;
	for(ans=l=r=0, que[r++]=s; l!=r; ){
		 for(num=son[u=que[l++]].size(), i=0; i<num; i++){
			 if(pre[v=son[u][i]]!=s){
				 pre[v]=s;
				 ans+=size[s]*size[v];
				 que[r++]=v;
			 }
		 }
	}
	return ans;
}
void solve(){
	getSCC(n);
	int i, ans, u, v;
	e* cur;
	for(i=0; i<scnt; i++){
		son[i].clear();
		size[i]=0;
	}
	for(i=0; i<n; i++){
		size[u=id[i]]++;
		for(cur=fir[i]; cur; cur=cur->nxt){
			if((v=id[cur->v])!=u){
				son[u].push_back(v);
			}
		}
	}
	for(ans=i=0; i<scnt; i++){
		ans += size[i]*(size[i]-1);
		pre[i]=-1;
	}
	for(i=0; i<scnt; i++){
		ans+=BFS(i);
	}
	printf("%d\n", ans);
}
int main(){
	
	int t;
	scanf("%d", &t);
	while(t--){
		input();
		solve();
	}
	return 0;
}