Pagini recente » Cod sursa (job #966617) | Cod sursa (job #2751257) | Cod sursa (job #772134) | Istoria paginii utilizator/snavenport | Cod sursa (job #2796940)
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <stack>
using namespace std;
//ifstream fin("bfs.in");
//ofstream fout("bfs.out");
//ifstream fin("dfs.in");
//ofstream fout("dfs.out");
ifstream fin("biconex.in");
ofstream fout("biconex.out");
int viz[100001];
int min_pos[100001];
stack <int> node_order;
int counter=0;
vector<int>biconex[100001];
class grafMare
{
int N,M;
vector <int> graf[100001];
public:
grafMare(){};
void citireBFS();
void citireDFS();
void actualDFS(int);
void citire_biconex();
void add_a_biconex(int,int);
void DFS_biconex(int,int,int);
};
void grafMare::add_a_biconex(int first, int i)
{
counter++;
while(node_order.top()!=i)
{
biconex[counter].push_back(node_order.top());
node_order.pop();
}
biconex[counter].push_back(node_order.top());
node_order.pop();
biconex[counter].push_back(first);
}
void grafMare::citire_biconex()
{
fin>>N>>M;
for(int i=0;i<M;i++)
{
int a,b;
fin>>a>>b;
graf[a].push_back(b);
graf[b].push_back(a);
}
}
void grafMare::DFS_biconex(int current_node, int current_pos, int tata_node)
{
min_pos[current_node]=current_pos;
node_order.push(current_node);
for(auto i : graf[current_node])
{
if(!min_pos[i]) //dfs
{
DFS_biconex(i, current_pos+1, current_node);
min_pos[current_node]=min(min_pos[current_node], min_pos[i]+1); // actualizez levelul minim in caz ca baiatul urmator are traseu mai scurt de la un nod mai devreme, dupa ce intra in else if(desen 2, 7-8, 1-8)
if(min_pos[i] > current_pos) // asta e punct de articulatie, daca n ar respecta cond asta, ins ca exista alt traseu care mentine conditia cu conex
add_a_biconex(current_node,i);
}
else if(i!=tata_node)
min_pos[current_node]=min(min_pos[current_node], min_pos[i]+1);
}
}
void grafMare::citireBFS()
{
fin>>N>>M;
int start;
fin>>start;
int a,b;
for(int i=0;i<M;i++)
{
fin>>a>>b;
graf[a].push_back(b);
}
int sol[100001];
for(int i=0;i<N+1;i++)
sol[i]=-1;
queue <int> q;
q.push(start);
sol[start]=0;
while(!q.empty())
{
int first=q.front();
q.pop();
for(int vecin : graf[first])
{
if(sol[vecin]==-1)
{
sol[vecin]=sol[first]+1;
q.push(vecin);
}
}
}
for(int i=1;i<N+1;i++)
fout<<sol[i]<<" ";
}
void grafMare::actualDFS(int index)
{
for(int vecin : graf[index])
if(!viz[vecin])
{
viz[vecin]=1;
actualDFS(vecin);
}
}
void grafMare::citireDFS()
{
fin>>N>>M;
int start=1;
int a,b;
for(int i=0;i<M;i++)
{
fin>>a>>b;
graf[a].push_back(b);
graf[b].push_back(a);
}
for(int i=0;i<N+1;i++)
viz[i]=0;
for(int i=1;i<N+1;i++)
if(!viz[i])
{
counter++;
actualDFS(i);
}
fout<<counter;
}
int main()
{
grafMare gm;
//gm.citireBFS();
gm.citire_biconex();
fout<<counter;
for(int i=0;i<counter;i++)
{
for(auto j : biconex[i])
fout<<j<<" ";
fout<<"\n";
}
}