| 试题编号： | 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 样例说明  城市间的连接如图所示。有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。 |
问题链接：CCF201509试题。
问题描述：（参见上文）。
问题分析：这是一个强联通图的问题，用Tarjan算法来解决。另外一个算法是kosaraju算法，也用于解决强联通图问题。
程序说明：本程序采用Tarjan算法。主函数main()中，创建图对象是参数本应该用n，但是提交后出现了运行错误，所有改成n+1。程序通过使用Tarjan算法类（参见以下链接）来实现，做了简单修改，使用变量ans来存储结果，其中增加了中间变量count。
求得强联通子图后，对于每一个强联通子图如果有k个结点，若k>1则强联通对结点的数量为k*(k-1)/2，若k=1则为0。
相关链接：Tarjan算法查找强联通组件。
提交后得100分的C++语言程序如下：
/* CCF201509-4 高速公路 */#include <iostream>
#include <list>
#include <stack>using namespace std;const int NIL = -1;int ans = 0;// A class that represents an directed graph
class Graph
{int V; // No. of verticeslist<int> *adj; // A dynamic array of adjacency lists// A Recursive DFS based function used by SCC()void SCCUtil(int u, int disc[], int low[],stack<int> *st, bool stackMember[]);
public:Graph(int V); // Constructorvoid addEdge(int v, int w); // function to add an edge to graphvoid SCC(); // prints strongly connected components
};Graph::Graph(int V)
{this->V = V;adj = new list<int>[V];
}void Graph::addEdge(int v, int w)
{adj[v].push_back(w);
}// A recursive function that finds and prints strongly connected
// components using DFS traversal
// u --> The vertex to be visited next
// disc[] --> Stores discovery times of visited vertices
// low[] -- >> earliest visited vertex (the vertex with minimum
// discovery time) that can be reached from subtree
// rooted with current vertex
// *st -- >> To store all the connected ancestors (could be part
// of SCC)
// stackMember[] --> bit/index array for faster check whether
// a node is in stack
void Graph::SCCUtil(int u, int disc[], int low[], stack<int> *st,bool stackMember[])
{// A static variable is used for simplicity, we can avoid use// of static variable by passing a pointer.static int time = 0;// Initialize discovery time and low valuedisc[u] = low[u] = ++time;st->push(u);stackMember[u] = true;// Go through all vertices adjacent to thislist<int>::iterator i;for (i = adj[u].begin(); i != adj[u].end(); ++i){int v = *i; // v is current adjacent of 'u'// If v is not visited yet, then recur for itif (disc[v] == -1){SCCUtil(v, disc, low, st, stackMember);// Check if the subtree rooted with 'v' has a// connection to one of the ancestors of 'u'// Case 1 (per above discussion on Disc and Low value)low[u] = min(low[u], low[v]);}// Update low value of 'u' only of 'v' is still in stack// (i.e. it's a back edge, not cross edge).// Case 2 (per above discussion on Disc and Low value)else if (stackMember[v] == true)low[u] = min(low[u], disc[v]);}// head node found, pop the stack and print an SCCint w = 0; // To store stack extracted verticesint count = 0;if (low[u] == disc[u]){while (st->top() != u){w = (int) st->top();
// cout << w << " ";count++;stackMember[w] = false;st->pop();}w = (int) st->top();
// cout << w << "\n";count++;stackMember[w] = false;st->pop();}if(count > 1)ans += count * (count -1) / 2;
}// The function to do DFS traversal. It uses SCCUtil()
void Graph::SCC()
{int *disc = new int[V];int *low = new int[V];bool *stackMember = new bool[V];stack<int> *st = new stack<int>();// Initialize disc and low, and stackMember arraysfor (int i = 0; i < V; i++){disc[i] = NIL;low[i] = NIL;stackMember[i] = false;}// Call the recursive helper function to find strongly// connected components in DFS tree with vertex 'i'for (int i = 0; i < V; i++)if (disc[i] == NIL)SCCUtil(i, disc, low, st, stackMember);
}int main()
{int n, m, src, dest;cin >> n >> m;Graph g(n+1);for(int i=1; i<=m; i++) {cin >> src >> dest;g.addEdge(src, dest);}g.SCC();cout << ans << endl;return 0;
}
