有向图连通性的判定·Warshall

有向图连通性的判定

• 题目信息
• • 测试样例
• 解答

题目信息

判断一个图是否为强连通图、单向连通图、弱连通图。输入为有向图的邻接矩阵。
输入
第一行为正整数N（0 接下来N行，每行有N个数据，每个数据以空格分隔，代表邻接矩阵
注意：
输入的都是连通图。
输出：
输出有一行，字母A，B，C
A代表强连通图
B代表单向连通图
C代表弱连通图

测试样例

3
1 1 1
1 1 1
1 1 1

A

解答

#include using namespace std;
int a[1000][1000];
int N;int main()
{freopen("E://test.txt", "r", stdin);cin >> N;for (int i = 0; i < N; i++){for (int j = 0; j < N; j++){cin >> a[i][j];}a[i][i] = 1;}for (int i = 0; i < N; i++){for (int j = 0; j < N; j++){if (a[j][i]){for (int k = 0; k < N; k++){//逻辑加a[j][k] = a[j][k] | a[i][k];}}}}bool flag = false;for (int i = 0; i < N; i++){for (int j = 0; j < N; j++){if ((a[i][j] == 0) && (a[j][i] == 0)){cout << "C" << endl;return 0;}if (a[i][j] == 0){flag = true;}}}if (flag){cout << "B" << endl;}else{cout << "A" << endl;}return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！