该题目的意思是n个城市及其道路构成了一个有向图，众多城市中有一个是首都。现在求至少要添加多少条有向道路才能使从首都出发能到达任意城市
解题方法：先用tarjan算法求出各个SCC（强连通分量），将每个SCC看作一个整体，即用一个点来表示一个SCC，便得到一个DAG（有向无环图），该过程又可称为缩点。首都必然位于某个SCC中。求出其他SCC的入度。如果其他的某个SCC入度为0，则从首都的SCC出发无法到达该SCC，则必须修建一条从首都SCC出发到达该SCC的公路。因此，题目的答案就是除了首都所在的SCC以外，其他入度为０的SCC的个数。
#include <iostream> #include <vector> #include <stack> #include <set> #include <algorithm> using namespace std; int n,m,s; const int N = 10001; int DFN[N] = { 0 }; // DFN[i] 表示节点i在DFS过程中按访问先后顺序得到的编号，0表示尚未访问 int LOW[N]; // LOW[i]表示节点i在DFS中能回到的最早的节点的编号 int index = 0; // 用于在DFS过程中按访问先后顺序给每个节点赋以编号 int SCCNO = -1; // 用于给每个SCC赋以编号 int SCC[N]; // SCC[i] 表示节点i所在的SCC的编号 bool InStack[N]; // InStack[i]==true 表示节点u在栈中 stack<int> vstack; vector<int>G[N]; // 题目的原图，以邻接表方式储存 set<int>newG[N]; // 缩点后的新图，以邻接表方式储存，用set是为了避免重边（在这题里可忽略重边的影响） int in[N]={0},out[N]={0}; void suodian() { for(int u=0;u<n;++u) { for(auto v:G[u]) { if(SCC[u]!=SCC[v]) if(newG[SCC[u]].insert(SCC[v]).second) // 判断边SCC[u]->SCC[v]是否已经存在，以去除重边 in[SCC[v]]++,out[SCC[u]]++; } } } void tarjan(int u) { DFN[u] = LOW[u] = ++index; InStack[u] = true; vstack.push(u); for (int v : G[u]) { if (!DFN[v]) { tarjan(v); LOW[u] = min(LOW[u], LOW[v]); } else if (InStack[v]) { LOW[u] = min(LOW[u], DFN[v]); } } if (LOW[u] == DFN[u]) { ++SCCNO; while (1) { int t = vstack.top(); vstack.pop(); InStack[t] = false; SCC[t] = SCCNO; if (t == u) break; } } } int main() { cin>> n>>m>>s; s--; while(m--) { int u,v; cin >> u >> v; u--,v--; // 让节点从0开始计数 G[u].push_back(v); } for(int i=0;i<n;++i) { if(!DFN[i]) tarjan(i); } suodian(); int ans=0; for(int i=0;i<=SCCNO;++i) { if(!in[i]&&SCC[s]!=i) ans++; } cout << ans; return 0; }
