flag

藍橋杯第26天

題目介紹

問題描述
　　有一個n個結點m條邊的有向圖，請輸出他的關聯矩陣。
輸入格式
　　第一行兩個整數n、m，表示圖中結點和邊的數目。n<=100,m<=1000。
　　接下來m行，每行兩個整數a、b，表示圖中有(a,b)邊。
　　注意圖中可能含有重邊，但不會有自環。
輸出格式
　　輸出該圖的關聯矩陣，注意請勿改變邊和結點的順序。
樣例輸入
5 9
1 2
3 1
1 5
2 5
2 3
2 3
3 2
4 3
5 4
樣例輸出
1 -1 1 0 0 0 0 0 0
-1 0 0 1 1 1 -1 0 0
0 1 0 0 -1 -1 1 -1 0
0 0 0 0 0 0 0 1 -1
0 0 -1 -1 0 0 0 0 1

思路

首先要弄懂關聯矩陣是如何建立的，我們發現矩陣5行9列，說明行數為結點數目，列數為邊的數目。

矩陣橫向來看，1代表節點的出邊，-1代表節點的入邊，每行之和為節點的度
矩陣縱向來看，每列都只有一個1和-1，1對應的節點就是出節點，-1對應的是入節點
因此建立矩陣，我們只需要每列依次填入1和-1即可

代碼

import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner input=new Scanner(System.in);int n=input.nextInt();//結點數目int m=input.nextInt();//邊數目int [][]matrix=new int[n+1][m+1];for(int i=1;i<=m;i++){int a=input.nextInt();int b=input.nextInt();matrix[a][i]=1;matrix[b][i]=-1;}for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){System.out.print(matrix[i][j]+" ");}System.out.println();}} }

總結

以上是生活随笔為你收集整理的关联矩阵的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。