蓝桥杯算法训练—关联矩阵
这题首先要明白关联矩阵是怎么一回事。关联矩阵是用结点与支路的关系描述有向图的拓扑性质。一条支路连接某两个结点,则称该支路与这两个结点相关联。支路与结点的关联性质可以用关联矩阵描述。设有向图的结点数为 n,支路数为 b,且所有结点与支路均加以编号。于是,该有向图的关联矩阵为一个(n*b)阶的矩阵,用Aij 表示。它的每一行对应一个结点,每一列对应一条支路,它的任一元素 aij定义如下:
- a jk=1,表示支路k与节点j关联且它的方向背离结点.
- a jk=-1,表示支路k与节点j关联且它的方向指向结点.
- a jk=0,表示支路k与节点j无关联.
eg: 如下图的关联矩阵
代码如下:
#include<iostream>
using namespace std;
int main(){
int n,m,a[1000],b[1000];
cin>>n>>m;
for(int i=0;i<m;i++){
cin>>a[i]>>b[i];
}
for(int j=0;j<n;j++){
for(int k=0;k<m;k++){
if(a[k]==j+1){
cout<<"1"<<" ";
}
else if(b[k]==j+1){
cout<<"-1"<<" ";
}
else cout<<"0"<<" ";
}
cout<<endl;
}
return 0;
}