欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

有向图的邻接矩阵存储根计算

程序员文章站 2022-05-21 08:48:39
...
若有向图中存在一个顶点v,从v可以通过路径到达图中其他所有顶点,那么称v为该有向图的根。假设图G采用邻接矩阵存储,求有向图的所有根。

输入

第一行为一个整数n,表示顶点的个数(顶点编号为0到n-1),接下来是为一个n*n大小的整数矩阵,表示图的邻接关系。

输出

有向图的所有根。

样例输入

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;
}