| 问题描述： |
问题描述 某国有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 样例说明 
城市间的连接如图所示。有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分了。
|
