Pagini recente » Cod sursa (job #2130992) | Cod sursa (job #234450) | Cod sursa (job #2224852) | Cod sursa (job #1278066) | Cod sursa (job #2799145)
#include <iostream>
#include <list>
#include <fstream>
#include <stack>
#include <vector>
using namespace std;
// ifstream fin("input.txt");
// ofstream fout("output.txt");
ifstream fin("sortaret.in");
ofstream fout("sortaret.out");
class graf {
private:
int n;
bool este_orientat;
list<int> *ad;
public:
graf(int n=1, bool o=1) {
this->n = n;
this->este_orientat = o;
this->ad = new list<int>[n];
};
void adaug_muchie(int v, int w) {
if (este_orientat == 1)
this->ad[v].push_back(w);
else {
this->ad[v].push_back(w);
this->ad[w].push_back(v);
}
};
void BFS(int s);
void distante(int s);
void DFS(int s);
void DFS_recursiv(int s, bool *vizitat);
int nr_conexe();
int* sortaret();
void dfs_top(int &ind, int i, bool* vizitat, int* sortare);
};
void graf::BFS(int s) {
bool *vizitat = new bool[n];
for (int i = 0; i < n; i++) {
vizitat[i] = false;
}
list<int> coada;
vizitat[s] = true;
coada.push_back(s);
while(!coada.empty()) {
list<int>::iterator i;
s = coada.front();
fout << s << " ";
// fout << s+1 << " ";
coada.pop_front();
for (i = ad[s].begin(); i != ad[s].end(); i++) {
if (vizitat[*i] == false) {
vizitat[*i] = true;
coada.push_back(*i);
}
}
}
delete[] vizitat;
}
void graf::distante(int s) {
bool *vizitat = new bool[n];
int *distante = new int[n];
for (int i = 0; i < n; i++) {
vizitat[i] = false;
distante[i] = -1;
}
list<int> coada;
vizitat[s] = true;
coada.push_back(s);
distante[s] = 0;
while(!coada.empty()) {
list<int>::iterator i;
s = coada.front();
coada.pop_front();
for (i = ad[s].begin(); i != ad[s].end(); i++) {
if (vizitat[*i] == false) {
vizitat[*i] = true;
distante[*i] = distante[s] + 1;
coada.push_back(*i);
}
}
}
for (int i = 0; i < n; i++) {
fout << distante[i] << " ";
}
delete[] vizitat;
delete[] distante;
}
void graf::DFS(int s) {
bool *vizitat = new bool[n];
for (int i = 0; i < n; i++) {
vizitat[i] = false;
}
DFS_recursiv(s, vizitat);
delete[] vizitat;
}
void graf::DFS_recursiv(int s, bool *vizitat) {
vizitat[s] = true;
// fout << s << " ";
list<int>::iterator it;
for (it = ad[s].begin(); it != ad[s].end(); it++) {
if (!vizitat[*it])
DFS_recursiv(*it, vizitat);
}
}
int graf::nr_conexe() {
bool *vizitat = new bool[n];
for (int i = 0; i < n; i++) {
vizitat[i] = false;
}
int nr = 0;
for (int i = 0; i < n; i++) {
if (!vizitat[i]) {
DFS_recursiv(i, vizitat);
nr ++;
}
}
delete[] vizitat;
return nr;
}
int* graf::sortaret() {
bool *vizitat = new bool[n];
int *sortare = new int[n];
for (int i = 0; i < n; i++) {
vizitat[i] = false;
sortare[i] = -1;
}
int ind = n - 1;
for (int i = 0; i < n; i++) {
if (!vizitat[i]) {
dfs_top(ind, i, vizitat, sortare);
}
}
delete[] vizitat;
return sortare;
}
void graf::dfs_top (int &ind, int i, bool* vizitat, int* sortare) {
vizitat[i] = true;
list<int>::iterator it;
for (it = ad[i].begin(); it != ad[i].end(); it++) {
if (!vizitat[*it]) {
dfs_top(ind, *it, vizitat, sortare);
}
}
sortare[ind] = i;
ind --;
}
int main() {
int n, m, s, a, b;
fin >> n >> m;
graf g(n, 1);
for (int i = 0; i < m; i++) {
fin >> a >> b;
g.adaug_muchie(a-1, b-1);
}
int* p = g.sortaret();
for (int i = 0; i < n; i++) {
fout << p[i] + 1 << " ";
}
delete[] p;
return 0;
}