文章目錄

• • • 題目解答
    • 題目鏈接

題目解答

來源：acwing

分析：

這題就是判斷每個點(diǎn)的連通性，如果能夠到達(dá)所有的n個點(diǎn)，就表示該點(diǎn)滿足題意。 這里的連通性指的是自己沿著正向邊能夠到達(dá)哪些點(diǎn)，還有就是哪些點(diǎn)沿著正向邊能夠到達(dá)該點(diǎn)，這都算該點(diǎn)可以到達(dá)的點(diǎn)。

這就啟發(fā)我們建兩次圖，一次正向，統(tǒng)計(jì)該點(diǎn)可以到達(dá)哪些點(diǎn)；建第二次圖是反向建立，這樣可以統(tǒng)計(jì)原來哪些點(diǎn)可以到達(dá)該點(diǎn)。分別做好標(biāo)記，然后統(tǒng)計(jì)點(diǎn)的個數(shù)即可。

AC代碼

#include<bits/stdc++.h> using namespace std;const int N = 1010, M = 20010; int n,m; // 建兩次圖，一次正向建圖，一次反向建圖 int h1[N], h2[N],e[M], ne[M], idx; bool st1[N], st2[N];void add(int h[], int a, int b){e[idx] =b , ne[idx] = h[a], h[a] = idx ++; }// dfs遍歷u點(diǎn)，看u點(diǎn)能夠連通哪些點(diǎn) void dfs(int u, int h[], bool st[]){st[u] = true;for(int i = h[u];~i; i = ne[i]){int j = e[i];if(!st[j]) dfs(j, h, st);} }int main(){cin >> n >> m;memset(h1, -1, sizeof h1);memset(h2, -1, sizeof h2);while(m --){int a, b;cin >> a >> b;add(h1, a, b), add(h2 ,b, a);}int res = 0;// n個點(diǎn)都進(jìn)行dfs，看是否和所有點(diǎn)連通for(int i =1; i <= n; i ++){memset(st1, 0, sizeof st1);memset(st2, 0, sizeof st2);dfs(i, h1, st1);dfs(i, h2, st2);int s = 0; // 統(tǒng)計(jì)連通個數(shù)（包括正向和反向）for(int j = 1; j <=n; j ++){if(st1[j] || st2[j]) s++;}if(s == n) res ++;}cout << res << endl; }

題目鏈接

https://www.acwing.com/problem/content/3253/

總結(jié)

以上是生活随笔為你收集整理的CSP认证201709-4通信网络[C++题解]：dfs、建立两张图：正向建图和反向见图、统计联通点的个数的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。