Pagini recente » Cod sursa (job #1906917) | Cod sursa (job #1314425) | Cod sursa (job #735848) | Cod sursa (job #2232331) | Cod sursa (job #2915513)
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <stack>
using namespace std;
class graf {
vector < bool > vis;
vector < vector < int > > muchii;
void dfs(int node) {
vis[node] = true;
for (int index = 0; index < muchii[node].size(); ++index) {
int nextNode = muchii[node][index];
if (!vis[nextNode]) {
dfs(nextNode);
}
}
}
int numarComponenteConexe() {
int counter = 0;
int n = muchii.size() - 1;
vis.resize(n + 1, false);
for (int node = 1; node <= n; ++node)
if (!vis[node]) {
++counter;
dfs(node);
}
return counter;
}
vector < int > bfs(int sursa) {
int n = muchii.size() - 1;
queue < int > coadaBfs;
vector < int > listaBfs;
listaBfs.resize(n + 1, -1);
listaBfs[sursa] = 0;
coadaBfs.push(sursa);
while (!coadaBfs.empty()) {
int nod = coadaBfs.front();
coadaBfs.pop();
for (int i = 0; i < muchii[nod].size(); ++i)
if (listaBfs[muchii[nod][i]] == -1) {
listaBfs[muchii[nod][i]] = listaBfs[nod] + 1;
coadaBfs.push(muchii[nod][i]);
}
}
return listaBfs;
}
void dfsSortareTopologica(int nod, stack < int > &topo) {
vis[nod] = 1;
for (int i = 0; i < muchii[nod].size(); ++i)
if (vis[muchii[nod][i]] == 0)
dfsSortareTopologica(muchii[nod][i], topo);
topo.push(nod);
}
public:
void dfsInfoarena() {
ifstream in("dfs.in");
ofstream out("dfs.out");
int n, m, x, y;
in >> n >> m;
muchii.resize(n + 1);
for (int index = 1; index <= m; ++index) {
in >> x >> y;
muchii[x].push_back(y);
muchii[y].push_back(x);
}
out << numarComponenteConexe();
}
void bfsInfoarena() {
ifstream in("bfs.in");
ofstream out("bfs.out");
int n, m, nod, x, y;
in >> n >> m >> nod;
muchii.resize(n + 1);
for (int index = 1; index <= m; ++index) {
in >> x >> y;
muchii[x].push_back(y);
}
vector < int > raspuns = bfs(nod);
for (int i = 1; i <= n; ++i)
out << raspuns[i] << " ";
}
void sortareTopologicaInfoarena() {
ifstream in("sortaret.in");
ofstream out("sortaret.out");
int n, m, x, y;
stack < int > topo;
in >> n >> m;
vis.resize(n + 1, false);
muchii.resize(n + 1);
for (int index = 1; index <= m; ++index) {
in >> x >> y;
muchii[x].push_back(y);
}
for (int i = 1; i<= n; ++i)
if (vis[i] == 0)
dfsSortareTopologica(i, topo);
while (!topo.empty()) {
int val = topo.top();
topo.pop();
out << val << " ";
}
}
};
int main()
{
graf g;
g.sortareTopologicaInfoarena();
return 0;
}