Pagini recente » Cod sursa (job #2353695) | Cod sursa (job #492649) | Cod sursa (job #2830869) | Cod sursa (job #729070) | Cod sursa (job #2969151)
#include <iostream>
#include <vector>
#include <fstream>
#include <queue>
using namespace std;
ifstream in("sortaret.in");
ofstream out("sortaret.out");
const int dim = 1e5 + 5;
int n,m, viz[dim], distante[dim], s, in_deg[dim];
vector<int> vec_nocost[dim];
void Citeste_nocost() {
in >> n >> m;
// in >> s;
for (int i=0, x, y; i<m; i++) {
in >> x >> y;
in_deg[y]++;
vec_nocost[x].push_back(y);
// vec_nocost[y].push_back(x);
}
}
void DFS(int nod) {
viz[nod] = 1;
for (auto y:vec_nocost[nod]) {
if (!viz[y]) {
DFS(y);
}
}
}
void BFS(int start) {
for (int i=1; i<=n; i++) {
distante[i] = -1;
}
distante[start] = 0;
queue<int> q;
q.push(start);
viz[start] = 1;
while (!q.empty()) {
int nod = q.front();
q.pop();
for (auto y:vec_nocost[nod]) {
if (!viz[y]) {
viz[y] = 1;
distante[y] = distante[nod] + 1;
q.push(y);
}
}
}
for (int i=1; i<=n; i++) {
out << distante[i] << " ";
}
}
int Nr_CompConexe() {
int cnt = 0;
for (int i=1; i<=n; i++) {
if (!viz[i]) {
cnt++;
DFS(i);
}
}
return cnt;
}
vector<int> SortareTopologicaDFS() {
}
vector<int> SortareTopologicaBFS() {
queue<int> q;
vector<int> rasp;
for (int i=1; i<=n; i++) {
if (in_deg[i] == 0) {
q.push(i);
}
}
while (!q.empty()) {
int nod = q.front();
q.pop();
rasp.push_back(nod);
for (auto y:vec_nocost[nod]) {
in_deg[y]--;
if (in_deg[y] == 0) {
q.push(y);
}
}
}
return rasp;
}
void AfisVector(vector<int> &vec) {
for (auto y:vec) {
out << y << " ";
}
}
int main() {
Citeste_nocost();
vector<int> rasp = SortareTopologicaBFS();
AfisVector(rasp);
return 0;
}