编程介的小学生 2019-11-30 21:53 采纳率: 20.5%
浏览 110

Arborescence Counting

Problem Description
"In graph theory, an arborescence is a directed graph in which, for a vertex v called the root and any other vertex u, there is exactly one directed path rom v to u. In other words, an arborescence is a directed, rooted tree in which all edges point away from the root. Every arborescence is a directed acyclic graph."-- from Wikipedia, the free encyclopedia

You are given a directed graph with N vertices, and your task is to count the number of different arborescences of size N that can be found in the given graph.

Two arborescences are considered different when they consist of different edges.

Input
Input consists of multiple test cases.
For each test case, the first line contains one integer N described as above.
N lines follows, each consists of N characters, either '0' or '1', representing the adjacency matrix of the graph.
The directed graph contains edge (i,j) if and only if the jth character of the ith line of the matrix is '1'.
The graph consists of no more than 8 vertices.
End of input is indicated by a line consisting of a single 0.

Output
For each test case, output one line consisting of one single integer, the number of arborescences.

Sample Input
2
00
00
2
01
10
0

Sample Output
0
2

  • 写回答

0条回答 默认 最新

    报告相同问题?

    悬赏问题

    • ¥15 求差集那个函数有问题,有无佬可以解决
    • ¥15 【提问】基于Invest的水源涵养
    • ¥20 微信网友居然可以通过vx号找到我绑的手机号
    • ¥15 寻一个支付宝扫码远程授权登录的软件助手app
    • ¥15 解riccati方程组
    • ¥15 display:none;样式在嵌套结构中的已设置了display样式的元素上不起作用?
    • ¥15 使用rabbitMQ 消息队列作为url源进行多线程爬取时,总有几个url没有处理的问题。
    • ¥15 Ubuntu在安装序列比对软件STAR时出现报错如何解决
    • ¥50 树莓派安卓APK系统签名
    • ¥65 汇编语言除法溢出问题