试题编号： 201509-4
试题名称： 高速公路
时间限制： 1.0s
内存限制： 256.0MB
问题描述： 问题描述 某国有n个城市，为了使得城市间的交通更便利，该国国王打算在城市之间修一些高速公路，由于经费限制，国王打算第一阶段先在部分城市之间修一些单向的高速公路。
　　现在，大臣们帮国王拟了一个修高速公路的计划。看了计划后，国王发现，有些城市之间可以通过高速公路直接（不经过其他城市）或间接（经过一个或多个其他城市）到达，而有的却不能。如果城市A可以通过高速公路到达城市B，而且城市B也可以通过高速公路到达城市A，则这两个城市被称为便利城市对。
　　国王想知道，在大臣们给他的计划中，有多少个便利城市对。 输入格式 输入的第一行包含两个整数n, m，分别表示城市和单向高速公路的数量。
　　接下来m行，每行两个整数a, b，表示城市a有一条单向的高速公路连向城市b。 输出格式 输出一行，包含一个整数，表示便利城市对的数量。 样例输入 5 5
1 2
2 3
3 4
4 2
3 5 样例输出 3 样例说明 ccf高速公路-编程之家
　　城市间的连接如图所示。有3个便利城市对，它们分别是(2, 3), (2, 4), (3, 4)，请注意(2, 3)和(3, 2)看成同一个便利城市对。 评测用例规模与约定 前30%的评测用例满足1 ≤ n ≤ 100, 1 ≤ m ≤ 1000；
　　前60%的评测用例满足1 ≤ n ≤ 1000, 1 ≤ m ≤ 10000；
　　所有评测用例满足1 ≤ n ≤ 10000, 1 ≤ m ≤ 100000。
一开始的想法是深搜每一个结点，这样就能知道它可以到达的所有结点，然后存到数组里，等知道所有结点可以到达的所有节点之后，对数组的一次遍历就可以解决了，不过O((N+M)*N)的算法显然只能得60分。
#include<iostream>
#include<vector>
#define MAX_VERTEX 10005
using namespace std;
int m, n;
vector<int> map[MAX_VERTEX];
bool canArrive[MAX_VERTEX][MAX_VERTEX];
bool visited[MAX_VERTEX];
void deepFirstSearch(int chufadian,int i)
{
 canArrive[chufadian][i] = true;
 visited[i] = true;
 vector<int>::iterator vertex;
 for (vertex = map[i].begin(); vertex != map[i].end(); vertex++)
 {
  if (visited[*vertex] == false)
  {
   deepFirstSearch(chufadian,*vertex);
  }
 }
}
int main(void)
{
 int a, b, i,j;
 long long num=0;
 cin >> n >> m;
 for (i = 1; i <= m; i++)
 {
  cin >> a >> b;
  map[a].push_back(b);
  canArrive[a][b] = true;
 } for (i = 1; i <= n; i++)
  for (j = 1; j <= n; j++)
   canArrive[i][j] = false; for (i = 1; i <= n; i++)//这步时间复杂度太高了O((m+n)n)
 {
  for (j = 1; j <= n; j++)
   visited[j] = false;
  deepFirstSearch(i,i);
 } for (i = 1; i <= n; i++)
  for (j = i+1; j <= n; j++)
   if (canArrive[i][j] == true && canArrive[j][i] == true)
    num++;
 cout << num;
 return 0;
}
然后抽象程度这么高的问题肯定有人早就想出好的多的算法，在《数据结构和算法分析》这本书里看到一个没有写名字的（不过从巧妙程度看肯定是很出名的）算法，可以两次深搜解决。

#include<iostream>
#include<vector>
#define MAX_VERTEX 10005
using namespace std;
int m, n;
vector<int> map[MAX_VERTEX];
vector<int> deverseMap[MAX_VERTEX];
bool canArrive[MAX_VERTEX][MAX_VERTEX];
bool visited[MAX_VERTEX];
int bianhao[MAX_VERTEX];
int haoma = 0;
int shouldContinue(void)
{
 int i;
 for (i = 1; i <= n; i++)
 {
  if (visited[i] == false)
   return i;
 }
 return false;
}
void deepFirstSearch(int chufadian, int i)
{ visited[i] = true;
 vector<int>::iterator vertex;
 for (vertex = map[i].begin(); vertex != map[i].end(); vertex++)
  if (visited[*vertex] == false)
   deepFirstSearch(chufadian, *vertex);
 
 bianhao[i] = ++haoma;//生成该结点编号，此处代替了后序遍历深度优先生成的树 if (chufadian == i)//如果一次遍历结束
 {
  int xinchufadian;
  if (xinchufadian=shouldContinue())
  {
   deepFirstSearch(xinchufadian, xinchufadian);
  }
 }
}
void deverse_map(void)//反转图
{
 int i;
 for (i = 1; i <= n; i++)
 {
  vector<int>::iterator vertex;
  for (vertex = map[i].begin(); vertex != map[i].end(); vertex++)
  {
   deverseMap[*vertex].push_back(i);
  } }
}
int bianhaozuida(void)
{
 int i;
 int max=-1;
 int maxNumber=-1;
 for (i = 1; i <= n; i++)
 {
  if (visited[i] == false)
  {
   if (maxNumber < bianhao[i])
   {
    max = i;
    maxNumber = bianhao[i];
   }
  }
 }
 if (max == -1)
  return 0;
 return max;
}
void DFS(vector<int> &size,int chufadian, int i)
{
 (*(size.end()-1))= (*(size.end() – 1))+1;
 visited[i] = true;
 vector<int>::iterator vertex;
 for (vertex =deverseMap[i].begin(); vertex != deverseMap[i].end(); vertex++)
  if (visited[*vertex] == false)
   DFS(size,chufadian, *vertex);
 if (chufadian == i)//如果一次遍历结束
 {
  int xinchufadian;
  if (xinchufadian = bianhaozuida())
  {
   size.push_back(0);
   DFS(size,xinchufadian, xinchufadian);
  }
 }
}
int main(void)
{
 int a, b, i, j;
 long long num = 0;
 cin >> n >> m;
 for (i = 1; i <= m; i++)
 {
  cin >> a >> b;
  map[a].push_back(b);
 } for (i = 1; i <= n; i++)
  visited[i] = false; deepFirstSearch(1, 1); deverse_map(); for (i = 1; i <= n; i++)
  visited[i] = false; vector<int> size;
 size.push_back(0);
 int qidian=bianhaozuida();
 DFS(size,qidian,qidian); vector<int>::iterator sizeNum;
 for (sizeNum = size.begin(); sizeNum != size.end(); sizeNum++)
 {
  int oneSize = *sizeNum;
  num += oneSize*(oneSize-1)/2;
 }
 cout << num;
 return 0;
} 就100分了。