swust.oj.1072_综合

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

Time limit(ms): 5000

Memory limit(kb): 10000

Submission: 1907

Accepted: 1461

Accepted

邻接矩阵有向图

若有向图中存在一个顶点v，从v可以通过路径到达图中其他所有顶点，那么称v为该有向图的根。假设图G采用邻接矩阵存储，求有向图的所有根。

Description

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

Input

有向图的所有根。

Output

Sample Input

        01234
       

        #include<stdio.h>
#include<algorithm>
#include<math.h>
#include<string.h>
#include<iostream>
using namespace std;
int a[20][20];
int vs[20];
int n;void find(int i)
{vs[i] = 1;for (int j = 0; j < n; j++){if (a[i][j]&&!vs[j]){find(j);}}
}//查找能到哪里bool jude()
{for (int j = 0; j < n; j++){if (!vs[j])return false;}return true;
}//判断是否满足条件int main()
{while (cin >> n){for (int i = 0; i < n; i++){for (int j = 0; j < n; j++){cin >> a[i][j];}}for (int i = 0; i < n; i++){memset(vs, 0, sizeof(vs));find(i);if (jude())cout << i;}}return 0;
}
        
 
       