Pagini recente » Cod sursa (job #2489999) | Cod sursa (job #3245702) | Cod sursa (job #684269) | Cod sursa (job #1803319) | Cod sursa (job #2786086)
#include<fstream>
#include<vector>
#include<queue>
#include<cstring>
using namespace std;
class Graf {
int n;
int m;
vector<int> v[100002];
bool viz[100002];
public:
Graf(int n, int m, pair<int, int> muchii[], bool directed);
int nrComponenteConexe();
vector<int> bfs(int srs);
vector<int> sortareTopologica();
private:
void dfs(int nod);
void dfsSortare(int nod, vector<int> &noduriSortate);
};
Graf :: Graf(int n, int m, pair<int, int> muchii[], bool directed) {
this->n = n;
this->m = m;
for (int i = 1; i <= m; i++) {
v[ muchii[i].first ].push_back(muchii[i].second);
if (!directed) {
v[ muchii[i].second ].push_back(muchii[i].first);
}
}
}
int Graf :: nrComponenteConexe() {
for (int i = 1; i <= n; i++) {
viz[i] = false;
}
int nr = 0;
for (int i = 1; i <= n; i++) {
if (!viz[i]) {
nr++;
dfs(i);
}
}
return nr;
}
void Graf :: dfs(int nod) {
viz[nod] = true;
for (int i = 0; i < v[nod].size(); i++) {
if (!viz[ v[nod][i] ]) {
dfs(v[nod][i]);
}
}
}
vector<int> Graf :: bfs(int srs) {
vector<int> dist;
dist.resize(n + 1);
for (int i = 1; i <= n; i++) {
dist[i] = -1;
}
queue<int> q;
q.push(srs);
dist[srs] = 0;
while (!q.empty()) {
int nod = q.front();
for (int i = 0; i < v[nod].size(); i++) {
int vecin = v[nod][i];
if (dist[vecin] == -1) {
dist[vecin] = dist[nod] + 1;
q.push(vecin);
}
}
q.pop();
}
return dist;
}
vector<int> Graf :: sortareTopologica() {
vector<int> noduriSortate;
memset(viz, 0, sizeof(viz));
for (int i = 1; i <= n; i++) {
if (!viz[i]) {
dfsSortare(i, noduriSortate);
}
}
for (int i = 0; i < n / 2; i++) {
swap(noduriSortate[i], noduriSortate[n - i - 1]);
}
return noduriSortate;
}
void Graf :: dfsSortare(int nod, vector<int> &noduriSortate) {
viz[nod] = true;
for (int i = 0; i < v[nod].size(); i++) {
int vecin = v[nod][i];
if (!viz[vecin]) {
dfsSortare(vecin, noduriSortate);
}
}
noduriSortate.push_back(nod);
}
int n, m, i;
pair<int, int> muchii[1000005];
ifstream fin ("sortaret.in");
ofstream fout("sortaret.out");
int main() {
fin>> n >> m;
for (i = 1; i <= m; i++) {
fin>> muchii[i].first >> muchii[i].second;
}
Graf* graf = new Graf(n, m, muchii, true);
vector<int> noduriSortate = graf->sortareTopologica();
for (int i = 0; i < noduriSortate.size(); i++) {
fout<< noduriSortate[i] <<" ";
}
}