Pagini recente » Cod sursa (job #539573) | Cod sursa (job #146735) | Cod sursa (job #1165728) | Cod sursa (job #2473380) | Cod sursa (job #2969155)
#include <iostream>
#include <vector>
#include <fstream>
#include <queue>
#include <stack>
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];
stack<int> sortTop;
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);
}
}
sortTop.push(nod);
}
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> 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);*/
for (int i=1; i<=n; i++) {
if (!viz[i] && in_deg[i] == 0) {
DFS(i);
}
}
while (!sortTop.empty()) {
out << sortTop.top() << " ";
sortTop.pop();
}
return 0;
}