Pagini recente » Cod sursa (job #3313105) | Cod sursa (job #3313851) | Cod sursa (job #3305714) | Cod sursa (job #123681) | Cod sursa (job #2796370)
#include <bits/stdc++.h>
using namespace std;
ifstream f("sortaret.in");
ofstream g("sortaret.out");
class graf
{
int nr_noduri, nr_muchii;
vector<vector<int> > lista_muchii;
bool orientat;
void DFSx(int nod, vector<int>&v);
public:
graf();
graf(int nr_noduri, int nr_muchii, bool orientat);
~graf() {}
void BFS(int start);
void DFS(int start);
//void CTC_DFS(int k, vector<int>&vizitat);
//void DFS_GT(int k, vector<int>&vizitat);
//void CTC_final();
void dfs_mic(int x, vector<bool> &vizitat, stack<int>&stiva);
void TOPO();
};
graf::graf()
{
nr_noduri = 0;
nr_muchii = 0;
orientat = 0;
}
graf::graf(int nr_noduri, int nr_muchii, bool orientat)
{
int i = 0, nod1, nod2;
lista_muchii.resize(nr_noduri+1);
this->nr_noduri = nr_noduri;
this->nr_muchii = nr_muchii;
this->orientat = orientat;
while(i < nr_muchii)
{
f>>nod1>>nod2;
if(orientat)
lista_muchii[nod1].push_back(nod2);
else
{
lista_muchii[nod1].push_back(nod2);
lista_muchii[nod2].push_back(nod1);
}
i++;
}
}
///----------------------------------------------------------------------------------bfs
void graf::BFS(int inceput)
{
int i = 0, nod_curent;
queue<int> q;
vector<int>vizitat;
vector<int>distanta;
q.push(inceput);
do
{
vizitat.push_back(0);
distanta.push_back(-1);
i++;
}
while(i <= nr_noduri);
vizitat[inceput] = 1;
distanta[inceput] = 0;
while(!q.empty())
{
nod_curent = q.front();
q.pop();
for (auto j = lista_muchii[nod_curent].begin(); j != lista_muchii[nod_curent].end(); j++)
if(!vizitat[*j])
{
vizitat[*j] = 1;
q.push(*j);
distanta[*j] = distanta[nod_curent] + 1;
}
}
int marime = distanta.size();
for(i = 1; i < marime; i++)
g<<distanta[i]<<" ";
}
///----------------------------------------------------------------------------------DFS
void graf::DFSx(int start, vector<int> &vizitat)
{
vizitat[start] = 1;
auto jos = lista_muchii[start].begin();
auto sus = lista_muchii[start].end();
auto j = jos;
while(j != sus)
{
if(vizitat[*j] == 0)
DFSx(*j, vizitat);
j++;
}
}
void graf::DFS(int start)
{
int i = 0, nr_componente_conexe = 0, marime;
vector<int> vizitat;
do
{
vizitat.push_back(0);
i++;
}
while(i <= nr_noduri);
marime = vizitat.size();
for(i = 1; i < marime; i++)
if(vizitat[i] == 0)
{
DFSx(i,vizitat);
nr_componente_conexe++;
}
g<<nr_componente_conexe;
}
///----------------------------------------------------------------------------------CTC
/*void graf::CTC_DFS(int k, vector<int> &vizitat)
{
int i;
vizitat[k] = 1;
for(i = 1; i <= nr_noduri; i++)
if(!vizitat[i])
{
int marime = lista_muchii[k].size();
int ok = 0;
for(int j = 0; j <= marime && ok == 0; j++)
if(lista_muchii[k][j] == i)
{
ok = 1;
CTC_DFS(i,vizitat);
}
}
}
void graf::DFS_GT(int k, vector<int> &vizitat)
{
int i;
vizitat[k] = 1;
for(i = 1; i <= nr_noduri; i++)
if(vizitat[i] == 0)
{
int marime = lista_muchii[i].size();
int ok = 0;
for(int j = 0; j <= marime && ok == 0; j++)
if(lista_muchii[i][j] == k)
{
ok = 1;
DFS_GT(i,vizitat);
}
}
}
void graf::CTC_final()
{
vector<int> ctc;
vector<int> vizitat1;
vector<int> vizitat2;
int i = 0, j, k, nrc = 0;
for(i = 1; i <= nr_noduri; i++)
if(ctc[i] == 0)
{
k = 0;
do
{
vizitat1.push_back(0);
vizitat2.push_back(0);
i++;
}
while(i <= nr_noduri);
nrc++;
CTC_DFS(i, vizitat1);
DFS_GT(i, vizitat2);
for(j = 1; j <= nr_noduri; j++)
if(vizitat1[j] == 1 && vizitat2[j] == 1)
ctc[j] = nrc;
}
}
*/
void graf::dfs_mic(int x, vector<bool>&vizitat, stack<int> &stiva)
{
vizitat[x] = 1;
int marime = lista_muchii[x].size(), i = 1;
while(i < marime)
{
if(vizitat[lista_muchii[x][i]] == 0)
dfs_mic(lista_muchii[x][i], vizitat, stiva);
i++;
}
stiva.push(x);
}
void graf::TOPO()
{
stack <int> stiva;
vector<bool>vizitat;
int i = 0;
do{
vizitat.push_back(0);
i++;
}while(i <= nr_noduri);
for(i = 1; i <= nr_noduri; i++)
if(vizitat[i] == 0)
dfs_mic(i, vizitat, stiva);
while(stiva.empty() == 0)
{
g<<stiva.top()<<" ";
stiva.pop();
}
}
int main()
{
int n, m, s;
f>>n>>m;
//------------------|
//graf test(n,m,0); |
//test.DFS(1); |DFS
//------------------|
graf test(n,m,1);
test.TOPO();
return 0;
}