有向图的邻接矩阵存储根计算
程序员文章站
2022-05-21 08:48:39
...
若有向图中存在一个顶点v,从v可以通过路径到达图中其他所有顶点,那么称v为该有向图的根。假设图G采用邻接矩阵存储,求有向图的所有根。
输入
第一行为一个整数n,表示顶点的个数(顶点编号为0到n-1),接下来是为一个n*n大小的整数矩阵,表示图的邻接关系。
输出
有向图的所有根。
样例输入
5
0 1 0 0 0
0 0 1 1 0
0 0 0 1 0
1 0 0 0 1
1 0 0 0 0
样例输出
01234
#include<iostream>
#include<string.h>
using namespace std;
#define maxsize 105
int a[maxsize][maxsize];
int visted[105];
void findH(int v,int n)
{
int i;
visted[v] = 1;
for (i = 0; i < n; i++)
{
if (a[v][i] == 1 && visted[i] == 0)findH(i,n);
}
}
int main()
{
int n, i, j;
cin >> n;
for (i = 0; i < n; i++)
{
for (j = 0; j < n; j++)
{
cin >> a[i][j];
}
}
for (i = 0; i < n; i++)
{
memset(visted, 0, sizeof(visted));
findH(i,n);
for (j = 0; j < n; j++)
{
if (visted[j] == 0)break;
}
if (j == n)cout << i;
}
//system("pause");
return 0;
}
上一篇: 东汉王朝的大权不在皇帝手上!外戚宦官交替*是怎么回事?
下一篇: 图:最短路dijkstra算法