AtCoder Beginner Contest 292- E - Transitivity

Solost

2023 年 03 月 06 日

190 次浏览

暂无评论

1249字数

题目题解

![image.png](https://amarantos.oss-cn-hangzhou.aliyuncs.com/typecho/2023%2F03%2F06%2Fimage.png)

## solution

这道题目的大意是给一个有向图，然后问你从a-b,b-c且a-c连一条边且距离等于1的条数，正面来做这道题有一定的难度，这个数起来太麻烦，可以转换思路，例如，把他所有的从当前点到可以到达的点的数目全部数出来，那么，我们就得到了从a-b距离为1，2，3，4.....n的所有情况，但是，我们是从a-b-c所以长度至少为2，那我们计算的时候计算了长度为1的情况，我们给出边的时候就是长度为1，即a-b长度肯定是1，所以我们删去m即是所有的情况。

```cpp
#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <fstream>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <unordered_map>
#include <vector>

using namespace std;
#define x first
#define y second
#define endl '\n'
#define IOS                       \
    ios_base::sync_with_stdio(0); \
    cin.tie(0);                   \
    cout.tie(0);
typedef long long ll;
typedef pair<int, int> PII;
typedef unsigned long long ull;
const int INF = 0x3f3f3f3f, mod = 1000000007;
const int N = 2e5 + 10;
int n, m;
vector<int> v[20100];
// int v[2010][2010];
map<int, int> vis;
int res, ans;
int dfs(int u)
{
    vis[u] = 1;
    for(auto x : v[u]){
        if(!vis[x]){
            res++;
            vis[x] = 1;
            dfs(x);
        }
    }
    return res;
}

void solve()
{
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int a, b;
        cin >> a >> b;
            v[a].push_back(b);
    }
    for (int i = 1; i <= n; i++) {
        dfs(i);
        vis.clear();
    }
    cout << res - m << endl;
}
int main()
{
    IOS;
    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}
```

最后修改：2023 年 03 月 06 日