Cod sursa(job #3193352)

Utilizator dumitrache12Dumitrache Iulian dumitrache12 Data 14 ianuarie 2024 14:53:55
Problema BFS - Parcurgere in latime Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.75 kb
#include<bits/stdc++.h>
using namespace std;

const int N = 100009;

ifstream in ("bfs.in");
ofstream out("bfs.out");
// auto& in = cin;
// auto& out = cout;

vector<vector<int>> adj(N, vector<int>());
vector<int> dist(N, -1);
queue<pair<int, int>> q;
bool visited[N];

void bfs() {
	while(!q.empty()) {
		auto crt = q.front();
		q.pop();
		if(visited[crt.first])
			continue;
		dist[crt.first] = crt.second;
		visited[crt.first] = true;
		for(auto neighbor: adj[crt.first]) 
			if(!visited[neighbor])
				q.emplace(neighbor, crt.second+1);			
	}
}

int main(){
	int n, m, s, x, y;
	in>>n>>m>>s;
	for(int i = 0; i < m; i++) {
		in>>x>>y;
		adj[x].push_back(y);
	}
	q.emplace(s, 0);
	bfs();
	for(int i = 1; i <= n; i++)
		out<<dist[i]<<" ";
	out<<endl;
	return 0;
}