CCF 201509-4 高速公路(强连通分量)

【题意】

某国有n个城市，为了使得城市间的交通更便利，该国国王打算在城市之间修一些高速公路，由于经费限制，国王打算第一阶段先在部分城市之间修一些单向的高速公路。
现在，大臣们帮国王拟了一个修高速公路的计划。看了计划后，国王发现，有些城市之间可以通过高速公路直接（不经过其他城市）或间接（经过一个或多个其他城市）到达，而有的却不能。如果城市A可以通过高速公路到达城市B，而且城市B也可以通过高速公路到达城市A，则这两个城市被称为便利城市对。
国王想知道，在大臣们给他的计划中，有多少个便利城市对。

【分析】对于一个有N个点的强连通分量会产生N*(N-1)/2对便利城市对，所有强连通分量累加即可。

【AC CODE】125ms

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
#define rep(i,a,n) for(int i = a; i < n; i++)
#define repe(i,a,n) for(int i = a; i <= n; i++)
#define per(i,n,a) for(int i = n; i >= a; i--)
#define clc(a,b) memset(a,b,sizeof(a))
const int INF = 0x3f3f3f3f, MAXN = 10000+10, MAXM = 100000+10;
int head[MAXN],tol,nxt[MAXM],to[MAXM];
int n,pre[MAXN],sccno[MAXN],dfs_clock,scc_cnt;

void add_edge(int u, int v)
{
	nxt[tol] = head[u], to[tol] = v;
	head[u] = tol++;
}
stack<int> s;
int ans;
int dfs(int u)
{
	int lowu = pre[u] = ++dfs_clock;
	s.push(u);
	for(int i = head[u]; ~i; i = nxt[i])
	{
		int v = to[i];
		if(!pre[v])
		{
			int lowv = dfs(v);
			lowu = min(lowu,lowv);
		}
		else if(!sccno[v]) lowu = min(lowu,pre[v]);
	}
	if(lowu == pre[u])
	{
		int x,cnt = 0;
		scc_cnt++;
		do{
			x = s.top();s.pop();
			sccno[x] = scc_cnt;
			cnt++;
		}while(x != u);
		ans += cnt*(cnt-1)>>1;
	}
	return lowu;
}
int main()
{
#ifdef SHY
	freopen("d:\\1.txt", "r", stdin);
#endif
	int n,m;
	scanf("%d %d", &n,&m);
	clc(head,-1);
	tol = 0;
	rep(i,0,m)
	{
		int u,v;
		scanf("%d%d", &u,&v);
		add_edge(u,v);
	}
	ans = 0;
	repe(i,1,n)
	{
		if(!pre[i])
			dfs(i);
	}
	printf("%d\n", ans);
	return 0;
}