dfs 枚举

这道题目要判断的是：某个点是否跟所有点有关系，于是我们就声明一个st[][]数组。

$st[i][j]$：表示i能走到j

于是从每个点出发dfs一次，并标记每个点与其所有子孙节点存在关联；

最后为每个点检查一遍，是否与所有点存关联。（判断是否存在关联需要从两个角度出发，当且仅当两个点都无法相互到达才可以判断两个点不关联。）

#include <iostream>
#include <cstring>

using namespace std;

const int N = 1010 , M = 100010;

int e[M] , ne[M] , h[N] , idx;
bool st[N][N];
int n , m;

void add(int a , int b)
{
    e[idx] = b , ne[idx] = h[a] , h[a] = idx++;
}

void dfs(int u , int fa)
{
    if(st[fa][u]) return;

    st[fa][u] = true;
    for(int i = h[u] ; ~i ; i = ne[i])
    {
        int j = e[i];
        dfs(j , fa);
    }
}

bool check(int t)
{
    for(int i = 1 ; i <= n ; i++)
        if(!st[t][i] && !st[i][t])//当且仅当i和t无法相互到达，确定i和t不关联
            return false;
    return true;
}

int main()
{
    cin >> n >> m;
    memset(h , -1 , sizeof h);

    while(m--)
    {
        int a , b;
        cin >> a >> b;
        add(a , b);
    }

    for(int i = 1 ; i <= n ; i++)
        dfs(i , i);

    int ans = 0;
    for(int i = 1 ; i <= n ; i++)   
        ans += check(i);

    cout << ans << endl;
}