传递闭包

传递闭包

传递闭包

从数学上来说，传递闭包是在集合X上求包含关系R关系。从关系图的角度来说，就是如果原关系图上有x到y,则其传递闭包的关系图上就应有x从到y的边。通俗地讲，就是确定每个点是否能到达其他每个点。

for (int k = 1; k <= n; ++k)
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j)
            if (E[i][k] && E[k][j])
                E[i][j] = 1;

这道题判断是否有点无法通过其他的点访问，即E[i][j] == 0 && E[j][i] == 0

#include 
#include 
#include 
using namespace std;
int n, m;
int mp[110][110];
int main()
{
    while(cin >> n >> m)
    {
        memset(mp, 0, sizeof mp);
        while(m--)
        {
            int a, b;
            cin >> a >> b;
            mp[a][b] = 1;
        }
        for(int k = 1; k <= n; k++)
        {
            for(int i = 1; i <= n; i++)
            {
                for(int j = 1; j <= n; j++)
                {
                    if(mp[i][k] && mp[k][j])
                    mp[i][j] = 1;
                }
            }
        }
        int ans = 0; //判断孤岛
        for(int i = 1; i <= n; i++)
        {
            int flag = 1;
            for(int j = 1; j <= n; j++)
                if(i != j && !mp[i][j] && !mp[j][i])
                flag = 0;
            ans += flag;
        }
        
        cout << ans << endl;
    }
    return 0;
}