B3611题解

西江月·定风波 · 2023-08-17 09:53:08 · 题解

本题核心：如果 i 能到 j 并且 j 能到 k，那么 i 能到 k。

注意一个坑点：一个点到本身也需要经过其他点，否则也得是 0。

可以用 SPFA 解决。

#include<bits/stdc++.h>
using namespace std;
vector<int>G[201];
queue<int>q;
bool dis[201];
int x[201],y[201],r[201],n;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++){
            int x;
            cin>>x;
            if(x==1)G[i].push_back(j);
        }
    for(int s=1;s<=n;s++){
        memset(dis,0,sizeof dis);
        q.push(s);
        while(!q.empty()){
            int u=q.front();
            q.pop();
            for(int v=0;v<G[u].size();v++){
                if(!dis[G[u][v]]){
                    dis[G[u][v]]=1;
                    q.push(G[u][v]);
                }
            }
        }
        for(int i=1;i<=n;i++)cout<<dis[i]<<" ";
        cout<<"\n";
    }
}