为什么不能用邻接矩阵呢?
  • 板块P1551 亲戚
  • 楼主csq_pig
  • 当前回复5
  • 已保存回复5
  • 发布时间2023/10/6 22:47
  • 上次更新2024/8/16 22:23:51
查看原帖
为什么不能用邻接矩阵呢?
1073710
csq_pig楼主2023/10/6 22:47
#include <bits/stdc++.h>
using namespace std;
bool ok[5010][5010];
int main()
{
	int a,b,n,m,p;
	scanf("%d%d%d",&n,&m,&p);
	for (int i=1;i<=n;i++)
		ok[i][i]=true;
	for (int i=1;i<=m;i++) {
		scanf("%d%d",&a,&b);
		ok[a][b]=true;
		ok[b][a]=true;
		for (int j=1;j<=n;j++) {
			if (ok[b][j]) {
				ok[a][j]=true;
				ok[j][a]=true;
			}
			if (ok[a][j]) {
				ok[b][j]=true;
				ok[j][b]=true;
			}
		}
	} 
//	for (int i=1;i<=n;i++) {
//		for (int j=1;j<=n;j++)
//			if (ok[i][j]) cout<<"1 ";
//			else cout<<"0 ";
//		cout<<endl;
//	} 
	for (int i=1;i<=p;i++) {
		scanf("%d%d",&a,&b);
		if (ok[a][b]) cout<<"Yes"<<endl;
		else cout<<"No"<<endl; 
	}
	return 0;
}
2023/10/6 22:47
加载中...