Counting four cycles
InterviewTime limit2sMemory limit128 MB
Count ordered 4-vertex cycles in an undirected graph given as an N by N adjacency matrix with N up to 250.
- Level
Medium5 of 10
- Topics
- Graph, Combinatorics, Matrix
- Solved
- No attempts yet
Problem
You are given an undirected graph. Count the four cycles it contains.
A four cycle is a cycle of length 4 on four distinct vertices. Vertices in this order form one when they are pairwise distinct and , , , are all edges.
Orders that visit the vertices differently count as different four cycles. For example, 1 -> 2 -> 3 -> 4 -> 1 and 2 -> 3 -> 4 -> 1 -> 2 are counted separately.
Input
The first line has the number of vertices . ()
Each of the next lines holds one row of the adjacency matrix of the undirected graph, given as integers separated by spaces, each of them 0 or 1. is 1 when an edge joins vertex and vertex , and 0 when it does not. No is 1.
Output
Print the number of four cycles on one line.