#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>
#include <unordered_map>
#include <set>
#include <deque>
#include <queue>
#include <climits>
#include <string>
#define inf INT_MAX-1000000
#define Nmax 100001
using namespace std;
int Exercitiu = 4;
ifstream fin;
ofstream fout;
class graf
{
int n,m;
vector< vector< int> > adj;
public:
graf(const int &opt=0);
void setn(const int &);
void setm(const int &);
int getn();
int getm();
void BFS( int);
void DFS( int, bool*, int&);
void sortaret( int, bool*, stack< int>&);
void S_BFS();
void S_DFS();
void S_sortaret();
void apm();
void apm1();
void uneste(int x, int y, int tata[], int rang[]);
int find(int x, int tata[]);
void disjoint();
void dijkstra();
void dijkstra1();
void Bellman_Ford();
};
graf::graf(const int &opt)
{
switch (opt)
{
case 1:
case 3:
{
int x,y;
fin>>this->n>>this->m;
if (opt==1)
fin>>x;
this-> adj.resize(n+1);
for ( int i=0; i<this->m; ++i)
{
fin>>x>>y;
this-> adj[x].push_back(y);
}
break;
}
case 2:
{
int x,y;
fin>>this->n>>this->m;
this-> adj.resize(n+1);
for ( int i=0; i<this->m; ++i)
{
fin>>x>>y;
this-> adj[x].push_back(y);
this-> adj[y].push_back(x);
}
break;
}
default:
break;
}
}
void graf::setn(const int &n)
{
this->n=n;
}
void graf::setm(const int &m)
{
this->m=m;
}
int graf::getm()
{
return this->m;
}
int graf::getn()
{
return this->n;
}
void graf::S_BFS()
{
ifstream h;
int start;
h.open("bfs.in",std::ifstream::in);
h>>start>>start>>start;
h.close();
BFS(start);
}
void graf::BFS( int start)
{
int dist[this->n+1];
for ( int i=1; i<=n; ++i)
dist[i]=-1;
int i=0;
vector <int> queue;
queue.push_back(start);
dist[start]=0;
while (i<queue.size())
{
int start=queue[i++];
for ( int i=0; i<this-> adj[start].size(); ++i)
if (dist[this-> adj[start][i]]==-1)
{
queue.push_back(this-> adj[start][i]);
dist[this-> adj[start][i]]=dist[start]+1;
}
}
for ( int i=1; i<=n; ++i)
{
fout<<dist[i]<<" ";
}
}
void graf::S_DFS()
{
bool visited[this->n+1];
int cc;
for ( int i=1; i<=this->n; ++i)
visited[i]=false;
cc=0;
for ( int i=1; i<=this->n; ++i)
if (!visited[i])
{
cc++;
DFS(i,visited,cc);
}
fout<<cc;
}
void graf::DFS( int nod,bool visited[], int &cc)
{
visited[nod]=true;
for ( int i=0; i<this-> adj[nod].size(); ++i)
if (!visited[this-> adj[nod][i]])
DFS(this-> adj[nod][i],visited,cc);
}
void graf::S_sortaret()
{
bool visited[this->n+1];
stack < int> mystack;
int i;
for (i=1; i<=this->n; ++i)
visited[i]=false;
for (i=1; i<=this->n; ++i)
if (!visited[i])
sortaret(i, visited, mystack);
while (!mystack.empty())
{
//afisam in postordine invers
fout<<mystack.top()<<" ";
mystack.pop();
}
}
void graf::sortaret( int nod, bool visited[], stack< int> &mystack )
{
visited[nod]=true;
for ( int i=0; i<this-> adj[nod].size(); ++i)
if (!visited[ adj[nod][i]])
{
sortaret( adj[nod][i], visited, mystack);
}
//introducem nodurile in postordine (dupa ce ies din stiva) in stiva solutie
mystack.push(nod);
}
void graf::apm()
{
int x,y;
int cost_total=0;
fin>>this->n>>this->m;
int tata[n+1];
int inaltime[n+1];
vector<pair<int,pair<int,int> > > lista_muchii_greutati;
lista_muchii_greutati.resize(this->n+1);
vector<pair<int,int> > sol;
for ( int i=0; i<this->m; ++i)
{
int cost;
fin>>x>>y>>cost;
lista_muchii_greutati.push_back(make_pair(cost,make_pair(x,y)));
}
for ( int i=0; i<=n; ++i)
{
tata[i]=0;
inaltime[i]=1;
}
sort(lista_muchii_greutati.begin(),lista_muchii_greutati.end());
int nrm=0;
for ( int i=0; i<lista_muchii_greutati.size() && nrm!=this->n-1; ++i)
{
int x=lista_muchii_greutati[i].second.first,y=lista_muchii_greutati[i].second.second;
int cost_muchie=lista_muchii_greutati[i].first;
int rx=x,ry=y,aux;
while (tata[rx]!=0)
rx=tata[rx];
while (tata[ry]!=0)
ry=tata[ry];
if (rx==ry)
{
}
else
{
sol.push_back(make_pair(x,y));
++nrm;
cost_total+=cost_muchie;
int hx=inaltime[rx];
int hy=inaltime[ry];
if (hx<hy)
{
tata[rx]=ry;
inaltime[ry]=max(hy,hx+1);
}
else
{
tata[ry]=rx;
inaltime[rx]=max(hx,hy+1);
}
}
while (x!=rx)
{
aux=tata[x];
tata[x]=rx;
x=aux;
}
while (y!=ry)
{
aux=tata[y];
tata[y]=ry;
y=aux;
}
}
fout<<cost_total<<"\n"<<this->n-1<<"\n";
for ( int i=0; i<sol.size(); ++i)
fout<<sol[i].first<<" "<<sol[i].second<<"\n";
}
int graf::find(int x, int tata[])
{
while (x != tata[x])
{
x = tata[x];
find(x, tata);
}
return x;
}
void graf::uneste(int x, int y, int tata[], int rang[]) // reuniune dupa rang <=> atasez arborelui mai mare pe cel mai mic
{
x = find(x, tata);
y = find(y, tata);
if (rang[x] >= rang[y])
{
tata[y] = x;
rang[x] += rang[y];
}
else
{
tata[x] = y;
rang[y] += rang[x];
}
}
void graf::apm1()
{
vector<pair<int, pair<int, int> > > cost_muchie; // m.first == costul, m.second.first = x, m.second.second = y;
vector<pair<int, int> > sol;
int n, m, tata[Nmax], rang[Nmax];
int x, y, cost;
fin >> n >> m;
for (int i = 0; i < m; i++)
{
fin >> x >> y >> cost;
cost_muchie.push_back(make_pair(cost, make_pair(x, y)));
}
for (int i = 0; i < n; i++)
{
tata[i] = i; // parintele
rang[i] = 1; // dimensiunea arborelui (cati copii are in total) => initial fiecare nod reprez un arbore form doar din rad
}
cost = 0;
sort(cost_muchie.begin(), cost_muchie.end());
for (auto muchie : cost_muchie)
{
if (find(muchie.second.first, tata) != find(muchie.second.second, tata))
{
// cout << "a intrat in if pt " << muchie.second.first << " " << muchie.second.second << "\n";
sol.push_back(muchie.second);
uneste(muchie.second.first, muchie.second.second, tata, rang);
cost += muchie.first;
// cout << " => cost = " << cost << "\n";
}
}
fout << cost << endl << sol.size() << endl;
for (int i = 0; i < sol.size(); i++)
{
fout << sol[i].first << " " << sol[i].second << "\n";
}
}
void graf::disjoint()
{
int n,m;
fin>>n>>m;
int parents[n+1];
int rank[n+1];
for ( int i=0; i<=n; ++i)
{
parents[i]=0;
rank[i]=1;
}
int op,x,y;
while (fin>>op>>x>>y)
{
if (op==1) //union by rank
{
while (parents[x]!=0)
x=parents[x]; // la final in x va fi parintele abs al acestuia la fel si in y
while (parents[y]!=0)
y=parents[y];
int rx=rank[x];
int ry=rank[y];
// x=y deci au aceasi parinti abs atunci deja fac parte din aceasi comp deci nu facem nimic
// cazurile sunt pt noduri ce nu sunt deja in aceasi comp si trb facut "union"
//union leaga parinte abs de parinte abs si il leaga pe cel cu intaltimea mai mica la cel cu inaltimea mai mare
if (rx<ry) //
{
parents[x]=y;
rank[y]=max(ry,rx+1);
}
else
{
parents[y]=x;
rank[x]=max(rx,ry+1);
}
}
else // find + compression
{
int pa_x=x,pa_y=y,aux; // pa_x = parintele absolut al lui x , similar ry
while (parents[pa_x]!=0) // gasim parintele abs al lui x
pa_x=parents[pa_x];
while (parents[pa_y]!=0) //gasim parinte abs al lui y
pa_y=parents[pa_y];
if (pa_x==pa_y) // x si y au aceaselasi parinte absolut
fout<<"DA\n";
else
fout<<"NU\n";
while (x!=pa_x) //actualizam parintii absoluti pt actualul x si pt restul nodurilor legat de el
{
aux=parents[x];
parents[x]=pa_x;
x=aux;
}
while (y!=pa_y) // actualizam parintii absoluti pt actualul y si pt restul nodurilor legat de el
{
aux=parents[y];
parents[y]=pa_y;
y=aux;
}
}
}
}
void graf::dijkstra()
{
int x,y;
int i;
fin>>this->n>>this->m;
int value[this->n+1]; // in value se retin distantele de la nodul src la restul
vector<vector<pair<int,int> > > adj;
adj.resize(this->n+1);
set<pair<int,int> > set_cost_nod; // set_cost_nod retine nodurile inca neprocesate si costul pt a ajunge in ele
//folosim set pt ca atunci cand vom lua un alt nod vrem sa il luam pe cel cu costul minim
// ce se afla la un mom de timp in set_nod_cost, inseamna ca acele noduri nu au fost inca procesate.
for ( int i=0; i<this->m; ++i)
{
int cost;
fin>>x>>y>>cost;
adj[x].push_back(make_pair(y,cost));
}
for (i=1; i<=this->n; ++i)
{
value[i]=inf;
}
value[1]=0;
set_cost_nod.insert(make_pair(0,1)); // cost 0 pt nodul sursa 1
while (!set_cost_nod.empty())
{
int nod=(*set_cost_nod.begin()).second; //luam nodul curent
set_cost_nod.erase(set_cost_nod.begin()); // pop nod crr si cost
for (int i=0; i< adj[nod].size(); ++i)
{
int nod_dest= adj[nod][i].first; // nod_dest = este nodul destinatie de la care plecam din nodul crr("nod")
int cost_dest= adj[nod][i].second; // costul muchiei de la nod la nod_dest
if (value[nod]+cost_dest<value[nod_dest]) // value[nod] retine dist de la nodul src(1) la nodul crr (nod)
// adugam costul de la nod crr la nod dest sa vedem daca gasim o cale mai "ieftina" din nodul src(1) la nod dest
{
if (value[nod_dest]!=inf)
{
set_cost_nod.erase(set_cost_nod.find(make_pair(value[nod_dest],nod_dest)));
//in cazul in care value[nod_dest] !=inf adica dist din 1 la nod_dest a mai fost actualizata si totusi s-a gasit
//un drum mai scurt, vom scoate valoarea veche din set_nod_cost pt a o reactualiza mai jos in value si pt a face push
//in set la noua valoare pt nod_dest
}
//deci se respecta cond din if
value[nod_dest]=value[nod]+cost_dest; // actualizam noul cost pt nodul dest
set_cost_nod.insert(make_pair(value[nod_dest],nod_dest)); // inseram in set (costul de a ajung din src la nod_dest, nod dest)
// la urmatoarele iteratii se va lua nod_dest ca fiind noul nod crr
}
}
}
for ( int i=2; i<=this->n; ++i)
if (value[i]!=inf)
fout<<value[i]<<" ";
else
fout<<0<<" ";
}
void graf::dijkstra1(){
int x,y;
fin>>this->n>>this->m;
int m_adj[this->n][this->n];
for (int i=1;i<=this->n;i++)
for(int j=1;j<=this->n;j++)
m_adj[i][j]=0;
for (int i=1;i<=m;i++)
{
int cost;
fin>>x>>y>>cost;
m_adj[x][y]=cost;
m_adj[y][x]=cost;
}
for (int i=1;i<=this->n;i++)
{for(int j=1;j<=this->n;j++)
fout<<m_adj[i][j]<<" ";
fout<<endl;
}
int parent[this->n]; //Stores Shortest Path Structure
vector<int> value(this->n,INT_MAX); //Keeps shortest path values to each vertex from source
vector<bool> processed(this->n,false); //TRUE->Vertex is processed
//Assuming start point as Node-0
parent[1] = -1; //Start node has no parent
value[1] = 0; //start node has value=0 to get picked 1st
//Include (V-1) edges to cover all V-vertices
for(int i=1;i<this->n;++i)
{
//Select best Vertex by applying greedy method
int U;// = selectMinVertex(value,processed);
int minimum = INT_MAX;
int vertex;
for(int i=1;i<=this->n;++i)
{
if(processed[i]==false && value[i]<minimum)
{
vertex = i;
minimum = value[i];
}
}
U=vertex;
processed[U] = true; //Include new Vertex in shortest Path Graph
//Relax adjacent vertices (not yet included in shortest path graph)
for(int j=1;j<=this->n;++j)
{
/* 3 conditions to relax:-
1.Edge is present from U to j.
2.Vertex j is not included in shortest path graph
3.Edge weight is smaller than current edge weight
*/
if(m_adj[U][j]!=0 && processed[j]==false && value[U]!=INT_MAX
&& (value[U]+m_adj[U][j] < value[j]))
{
value[j] = value[U]+m_adj[U][j];
parent[j] = U;
}
}
}
fout<<endl;
for (int i=1;i<=this->n;i++)
{
fout<<value[i]<<" ";
}
}
void graf::Bellman_Ford()
{
int x,y;
int i,j,k;
fin>>this->n>>this->m;
int d[this->n+1];
vector<vector<pair<int,int> > > adj;
adj.resize(this->n+1);
for ( int i=0; i<this->m; ++i)
{
int cost;
fin>>x>>y>>cost;
adj[x].push_back(make_pair(y,cost));
}
for (i=1; i<=this->n; ++i)
d[i]=inf;
d[1]=0;
for (i=0; i<this->n-1; ++i)
{
for (j=1; j< adj.size(); ++j)
{
int nod_curent=j;
for (k=0; k< adj[j].size(); ++k)
{
int nod_dest= adj[j][k].first;
int cost_dest= adj[j][k].second;
cout<<"Muchia "<<nod_curent<<" "<<nod_dest<<" cu costul "<<cost_dest<<"\n";
if (d[nod_curent]+cost_dest<d[nod_dest])
{
d[nod_dest]=d[nod_curent]+cost_dest;
cout<<"Inlocuim distanta de la 1 la "<<nod_dest<<"cu distanta "<<d[nod_dest]<<"\n";
}
}
}
}
for (j=1; j< adj.size(); ++j)
{
int nod_curent=j;
for (k=0; k< adj[j].size(); ++k)
{
int nod_dest= adj[j][k].first;
int cost_dest= adj[j][k].second;
if (d[nod_curent]+cost_dest<d[nod_dest])
{
fout<<"Ciclu negativ!";
return;
}
}
}
for (i=2; i<=this->n; ++i)
fout<<d[i]<<" ";
}
int main()
{
switch (Exercitiu)
{
case 1:
{
fin.open ("bfs.in", std::ifstream::in);
fout.open ("bfs.out", std::ifstream::out);
graf a(1);
a.S_BFS();
fin.close();
fout.close();
break;
}
case 2:
{
fin.open ("dfs.in", std::ifstream::in);
fout.open ("dfs.out", std::ifstream::out);
graf a(2);
a.S_DFS();
fin.close();
fout.close();
break;
}
case 3:
{
fin.open("sortaret.in",std::fstream::in);
fout.open("sortaret.out",std::fstream::out);
graf a(3);
a.S_sortaret();
fin.close();
fout.close();
break;
}
case 4:
{
fin.open("apm.in",std::fstream::in);
fout.open("apm.out",std::fstream::out);
graf a;
a.apm1();
fin.close();
fout.close();
break;
}
case 5:
{
fin.open("disjoint.in",std::fstream::in);
fout.open("disjoint.out",std::fstream::out);
graf a;
a.disjoint();
fin.close();
fout.close();
break;
}
case 6:
{
fin.open("dijkstra.in",std::fstream::in);
fout.open("dijkstra.out",std::fstream::out);
graf a;
a.dijkstra();
fin.close();
fout.close();
break;
}
case 7:
{
fin.open("bellmanford.in",std::fstream::in);
fout.open("bellmanford.out",std::fstream::out);
graf a;
a.Bellman_Ford();
fin.close();
fout.close();
break;
}
default:
break;
}
}
vlad calomfirescu vlad-123-123