题目地址

C - Tour

https://atcoder.jp/contests/abc204/editorial/1991

問題描述

The republic of AtCoder has N cities numbered 1 through N and Mroads numbered 1 through M.

Road i leads from City A_i to City B_i, but you cannot use it to get from City B_i to City A_i.

Puma is planning her journey where she starts at some city, travels along zero or more roads, and finishes at some city.

How many pairs of cities can be the origin and destination of Puma's journey? We distinguish pairs with the same set of cities in different orders.

Constraints

2 \leq N \leq 2000
0 \leq M \leq \min(2000,N(N-1))
1 \leq A_i,B_i \leq N
A_i \neq B_i
(A_i,B_i) are distinct.
All values in input are integers.

Input

Input is given from Standard Input in the following format:

 N M
 A1 B1
 ...
 AM BM

Output

Print the answer.

Sample Input 1

Sample Output 1

We have seven pairs of cities that can be the origin and destination: (1,1),(1,2),(1,3),(2,2),(2,3),(3,2),(3,3).

Sample Input 2

3 0

Sample Output 2

We have three pairs of cities that can be the origin and destination: (1,1),(2,2),(3,3).

Sample Input 3

Sample Output 3

Every pair of cities can be the origin and destination.

题意

AtCoder王国有

N个编号为1到N的城市
M条编号为1到M的道路。

道路i从A_i市通往B_i市，但不能能用从B_i市通往A_i市。

彪马正在计划她的旅程，她从某个城市出发，沿着零条或多条道路旅行，然后在某个城市结束。

求有多少种起点和终点城市组合？

思路

固定起始点，然后遍历到达可能的城市
可以考虑使用DFS、BFS算法遍历

题解

小码匠: DFS

 int n;
 vector<bool>leaf(n);
 
 void dfs(int x, vector<vector<int>> &vvi) {
     if(leaf[x]) {
         return;
     }
     leaf[x] = true;
     for(auto a : vvi[x]) {
         dfs(a, vvi);
     }
 }
 
 void coder_solution() {
     // 提升cin、cout效率
     ios::sync_with_stdio(false);
     cin.tie(0);
     cout.tie(0);
     int m, temp = 0;
     cin >> n >> m;
     vector<vector<int>> vvi(n);
     int a, b;
     for (int i = 0; i < m; i++) {
         cin >> a >> b;
         vvi[a - 1].push_back(b - 1);
     }
     for (int i = 0; i < n; i++) {
         for (int j = 0; j < n; j++) {
             leaf[j] = false;
         }
         dfs(i, vvi);
         for (int j = 0; j < n; j++) {
             if (leaf[j]) {
                 temp++;
             }
         }
     }
 }

小码匠: BFS

 void best_solution() {
     ios::sync_with_stdio(false);
     cin.tie(0);
     cout.tie(0);
     int n, m;
     cin >> n >> m;
     int a, b;
     vector<vector<int>> vvi(n);
     for(int i = 0; i < m; i++) {
         cin >> a >> b;
         vvi[a - 1].push_back(b - 1);
     }
 
     vector<int> dist(n, -1);
     queue<int> que;
     dist[0] = 0;
     int v;
     int j = 0;
     for(int i = 0; i < n; i++) {
         que.push(i);
         dist[i] = 0;
         while(!que.empty()) {
             v = que.front();
             que.pop();
             for(auto next_v : vvi[v]) {
                 if (dist[next_v] != -1) {
                     continue;
                 }
                 dist[next_v] = dist[v] + 1;
                 que.push(next_v);
             }
         }
         j += n - count(dist.begin(), dist.end(), -1);
         dist.assign(n, -1);
     }
     cout << j;
 }

官方题解1：BFS

一些语法感觉有些诡异，例如第8行，第14行的循环语句，老码农建议不要学，不符合多数人习惯

 #include<bits/stdc++.h>
 using namespace std;
 
 int main(){
     int n, m;
     cin >> n >> m;
     auto e = vector(n, vector<int>());
     for(int i{}, a, b; i < (m); ++i){
         cin >> a >> b;
         --a, --b;
         e[a].push_back(b);
     }
     ll ans{};
     for(int s{}; s< (n); ++s){
         vector<bool> vis(n);
         vis[s] = true;
         queue<int> q;
         q.push(s);
         while(!q.empty()){
             ++ans;
             int i = q.front();
             q.pop();
             for(auto&j:e[i]) if(!vis[j]){
                 vis[j] = true;
                 q.push(j);
             }
         }
     }
     cout << ans << endl;
 }

官方题解2：DFS

 #include<bits/stdc++.h>
 
 using namespace std;
 const int MAX_N = 2000;
 vector<vector<int>> G;
 bool temp[MAX_N];
 
 void dfs(int v) {
     if (temp[v]) {
         return;
     }
     temp[v] = true;
     for (auto vv: G[v]){
         dfs(vv);
     }
 }
 
 int main() {
     int N, M;
     cin >> N >> M;
     G.resize(N);
     for (int i = 0; i < M; i++) {
         int a, b;
         cin >> a >> b;
         G[a - 1].push_back(b - 1);
     }
     int ans = 0;
     for (int i = 0; i < N; i++) {
         for (int j = 0; j < N; j++) {
             temp[j] = false;
         }
         dfs(i);
         for (int j = 0; j < N; j++) {
             if (temp[j]){
                 ans++;
             |
         }
     }
     cout << ans;
 }

广度优先搜索算法 (深度优先搜索和宽度优先搜索例题)

标签