题解

题解

虚空终端 · 发布于 2023-09-02 · 浏览 618 回复 5 
#include<iostream>
#include<cstring>
#include<queue>

using namespace std;

typedef pair<int,int> PII;

const int N=1e6+10;
const int M=2e6+10;
const int mod=100003;

int n,m,idx;
int e[M],ne[M],h[M],dist[N],cnt[N];
bool st[N];
 
void add(int a,int b)
{
	ne[idx]=h[a];
	e[idx]=b;
	h[a]=idx;
	idx++;
}

void bfs()
{
	queue<PII> q;
	q.push({1,0});
	st[1]=1;
	cnt[1]=1;
	dist[1]=0;
	while(!q.empty())
	{
		PII t=q.front();
		q.pop();
		dist[t.first]=t.second;
		for(int i=h[t.first];i!=-1;i=ne[i])
		{
			if(!st[e[i]])
			{
				st[e[i]]=1;
				q.push({e[i],t.second+1});
			}
			if(dist[e[i]]==t.second-1)
				cnt[t.first]+=cnt[e[i]];
		}
	}
	return;
}

int main()
{
	memset(h,-1,sizeof(h));
	memset(ne,-1,sizeof(ne));
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		int x,y;
		cin>>x>>y;
		add(x,y);
		add(y,x);
	}
	bfs();
	for(int i=1;i<=n;i++)
		cout<<cnt[i]<<endl;
	return 0;
 }

全部回复 共 5 条

  1. 刘谦 #1 ·

    include <bits/stdc++.h>

    include

    using namespace std; int cnt[100][100];

    int main() {

    int n;
cin >> n;
while (n--) {
	int a, b, c, d;
	cin >> a >> b >> c >> d;
	for (int i = a ; i <= b - 1; i++) {
		for (int j = c ; j <= d - 1; j++) {
			cnt[i][j] = 1;
		}
	}
}
int ans = 0;
for (int i = 0; i <= 100; i++) {
	for (int j = 0; j <= 100; j++) {
		if (cnt[i][j])
			ans++;
	}
}
cout << ans;
return 0;

    }

  2. 刘谦 #2 ·

    include <bits/stdc++.h>

    include

    using namespace std; int cnt[100][100];

    int main() {

    int n;
cin >> n;
while (n--) {
	int a, b, c, d;
	cin >> a >> b >> c >> d;
	for (int i = a ; i <= b - 1; i++) {
		for (int j = c ; j <= d - 1; j++) {
			cnt[i][j] = 1;
		}
	}
}
int ans = 0;
for (int i = 0; i < 100; i++) {
	for (int j = 0; j < 100; j++) {
		if (cnt[i][j])
			ans++;
	}
}
cout << ans;
return 0;

    }

  3. 刘谦 #3 ·

    include <bits/stdc++.h>

    include

    using namespace std; int cnt[100][100];

    int main() {

    int n;
cin >> n;
while (n--) {
	int a, b, c, d;
	cin >> a >> b >> c >> d;
	for (int i = a ; i <= b - 1; i++) {
		for (int j = c ; j <= d - 1; j++) {
			cnt[i][j] = 1;
		}
	}
}
int ans = 0;
for (int i = 0; i < 100; i++) {
	for (int j = 0; j < 100; j++) {
		if (cnt[i][j])
			ans++;
	}
}
cout << ans;
return 0;

    }

  4. 虚空终端 #4 楼主 ·

    大哥宁这个连输入都对不上吧啊喂

  5. 刹那(｡･∀･)ﾉﾞ #5 ·

    甚至3层循环嵌套2333

发表回复