社区微信群开通啦,扫一扫抢先加入社区官方微信群
社区微信群
代码:
#include <iostream>
#include <vector>
#include <stack>
using namespace std;
int dfs(vector<vector<int>>& cities, int k, vector<int>& temp)
{
int count = 0;
stack<int> stack;
vector<bool> visited(cities.size(), false);
stack.push(k);
while (!stack.empty())
{
int curNode = stack.top();
if (visited[curNode])
{
stack.pop();
}
else
{
visited[curNode] = true;
for (int i = 0; i < cities[curNode].size(); i++)
{
int v = cities[curNode][i];
if (!visited[v])
stack.push(v);
}
}
}
for (int i = 1; i< cities.size(); i++)
{
if (visited[i])
{
temp[i] = temp[i] + 1;//如果城市k能访问到城市i,则城市i的进入路线城市加1
++count;//记录能进入城市i的所有城市总和
}
}
return count;
}
int main()
{
int vertexNum = 0;
int edgesNum = 0;
cin >> vertexNum >> edgesNum;
vector<vector<int>> cities(vertexNum + 1, vector<int>());
for (int i = 0; i < edgesNum; i++)
{
int u, v;
cin >> u >> v;
cities[u].push_back(v);
}
vector<int> s_in(vertexNum + 1, 0);//记录能进入每个城市的总数量
vector<int> s_out(vertexNum + 1, 0);//记录每个城市到达其他城市的总数量
for (int i = 1; i <= vertexNum; i++)
{
s_out[i] = dfs(cities, i, s_in);
}
int importCityNum = 0;
for (int i = 1; i <= vertexNum; i++)
{
if (s_in[i] > s_out[i])
importCityNum++;
}
cout << importCityNum << endl;
}
如果觉得我的文章对您有用,请随意打赏。你的支持将鼓励我继续创作!