# Cod sursa(job #2809139)

Utilizator Data 26 noiembrie 2021 02:44:06 Sortare topologica 100 cpp-64 done Arhiva educationala 5.45 kb
``````#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <bitset>
#include<stack>
using namespace std;
///ifstream f("dfs.in");ofstream g ("dfs.out");
///ifstream f("bfs.in");ofstream g("bfs.out");
///ifstream f("biconex.in");ofstream g("biconex.out");
///ifstream f("ctc.in");ofstream g("ctc.out");
ifstream f("sortaret.in");ofstream g("sortaret.out");
int verif[100001],low[100001],cost[100001];
vector <int> muchii[100001], componente[100001];
vector<int> q[100001],w[100001],result[100001];
class graf{
private:
int n, m, x, y, nods,counter=0, cont=0;

vector<int> distanta{vector<int>(100001, -1)};
stack<int>stiva;
public:
graf(){}
graf (int n, int m)  ///constructor graf dfs / biconexe
{
this-> n = n;
this-> m = m;

for(int i=1; i<=m; i++){
f>>x>>y;
muchii[x].push_back(y);
muchii[y].push_back(x);
}
}
graf(int n, int m, int nods){ /// constructor graf bfs
this-> n = n;
this-> m = m;
this->nods=nods;
for(int i=1;i<=m;i++){
f>>x>>y;
muchii[x].push_back(y);
}
}
void citireCTC(int n, int m){ ///citire CTC
this-> n = n;
this-> m = m;
for(int i=1; i<=m;i++) {
int x,y;
f>>x>>y;
q[x].push_back(y);
w[y].push_back(x);
}
}
void citireTOPSORT(int n, int m){  ///citire TOPSORT
this-> n = n;
this-> m = m;
for (int i=1;i<=m;i++){
int x,y;
f>>x>>y;
muchii[x].push_back(y);
}
}
void dfs(int nod){    /// dfs simplu
verif[nod]=true;
for (int i=0; i<muchii[nod].size(); i++){
int vecin = muchii[nod][i];
if(verif[vecin]!=true)
dfs(vecin);
}
}
void bfs()   /// bfs simplu
{
int nod, vecin;
{
for (int i= 0;i<muchii[nod].size();i++)
{
vecin = muchii[nod][i];
if(distanta[vecin]==-1)
{
distanta[vecin]=distanta[nod]+1;
}
}
}
}

void dfsRez(){    /// rezolvare problema dfs
for (int i=1;i<=n;i++){
if (verif[i]!=true){
counter++;
dfs(i);
}
}
g<<counter;
}
void bfsRez(){ /// rezolvare problema bfs
distanta[nods]=0;
bfs();
for (int i=1;i<=n;i++){
g<<distanta[i] <<" ";
}

}

void biconexe(int nod,int parent){ ///biconexe
verif[nod]=true;
low[nod]=cost[nod]=cost[parent]+1;
stiva.push(nod);
for (int i=0;i<muchii[nod].size();i++){
if (muchii[nod][i] != parent){
if (verif[muchii[nod][i]])
low[nod]=min(low[nod],cost[muchii[nod][i]]);
else{
biconexe(muchii[nod][i],nod);
low[nod]=min(low[nod],low[muchii[nod][i]]);
if (low[muchii[nod][i]]>=cost[nod]){
cont++;
while (stiva.top()!=muchii[nod][i]){componente[cont].push_back(stiva.top());stiva.pop();}
componente[cont].push_back(muchii[nod][i]);stiva.pop();componente[cont].push_back(nod);
}
}
}
}
}

void biconexeRez(){ ///biconexe rezolvare
for (int i=1;i<=n;i++)
if (verif[i]==0)
biconexe(i,0);
g<<cont<<'\n';
for (int i=1;i<=cont;i++){
for (int j=componente[i].size()-1;j>=0;j--)
g<< componente[i][j]<<" ";
g<<'\n';
}
}
void dq(int nod){  ///ctc
verif[nod]=1;
for(int i=0; i<q[nod].size();i++){
int vecin=q[nod][i];
if(verif[vecin]==false)
dq(vecin);
}
stiva.push(nod);
}
void dw(int nod){  ///ctc
verif[nod]=2;
result[cont].push_back(nod);
for(int i=0;i<w[nod].size();i++){
int vecin=w[nod][i];
if(verif[vecin]==1)
dw(vecin);
}
}
void ctcRez(){ ///ctc
for(int i=1; i<=n; i++)
if(!verif[i])
dq(i);

while(!stiva.empty()){
int nod = stiva.top();
if(verif[nod] == 1){
cont++;
dw(nod);
}
stiva.pop();
}
g<<cont<<'\n';
for(int i=1; i<=cont;i++){
for(int j=0; j < result[i].size(); j++)
g<<result[i][j]<<' ';
g<<'\n';
}
}
void topsort(int nod){  ///topsort
verif[nod]=true;
for(int i=0;i<muchii[nod].size();i++){
int vecin = muchii[nod][i];
if (!verif[vecin])
topsort(vecin);
}
stiva.push(nod);
}
void topsortREZ(){ ///topsort
for(int i=1;i<=n;i++){
if(!verif[i])
topsort(i);
}
while(!stiva.empty()){
g<<stiva.top()<<" ";
stiva.pop();
}

}

virtual ~graf(){}
};
int main()
{
/// int n,m;f>>n>>m;graf g1(n,m);g1.dfsRez();     ///dfs 100p
/// int n,m,nods; f>>n>>m>>nods; graf g1(n,m,nods); g1.bfsRez(); ///bfs 100p
///int n,m;f>>n>>m;graf g1(n,m);g1.biconexeRez(); ///biconexe 100p
///int n,m;f>>n>>m;graf g1;g1.citireCTC(n,m);g1.ctcRez(); /// Componente tare conexe 100p
int n,m;f>>n>>m;graf g1; g1.citireTOPSORT(n,m);g1.topsortREZ(); ///Sortare Topologica 100p
return 0;
}
``````