Pagini recente » Cod sursa (job #3143585) | Cod sursa (job #638312) | Cod sursa (job #1832539) | Cod sursa (job #934798) | Cod sursa (job #2798819)
#include <bits/stdc++.h>
#include <fstream>
using namespace std;
vector<int>g[100005];
int low[100005];
int lvl[1000005];
vector<pair<int,int>> critice;
vector<pair<int,int>> mch_elim;
vector<vector<int>> comp_biconexe;
int vecin,nodCurent,lv,nrNoduri,nrMuchii;
ifstream in("biconex.in");
ofstream out("biconex.out");
void dfs(int nodCurent, int parinte, int l)
{
lvl[nodCurent]=l;
low[nodCurent]=l;
for(auto vecin : g[nodCurent])
{
if(lvl[vecin]==0)
{
dfs(vecin,nodCurent,l+1);
low[nodCurent]=min(low[nodCurent],low[vecin]);
}
else if(vecin!=parinte)
{
low[nodCurent]=min(low[nodCurent],lvl[vecin]);
}
}
if(low[nodCurent]==lvl[nodCurent]&& parinte!=-1)
{
critice.push_back({nodCurent,parinte});
}
}
void eliminare_muchii_critice()
{
for(auto& per:critice)
{
int from, to;
from = per.first;
to=per.second;
g[from].erase(find(g[from].begin(),g[from].end(), to)); //elimina muchiile crit gasite din graf
g[to].erase(find(g[to].begin(),g[to].end(),from));
}
}
void dfs2(int s)
{
lvl[s] = 1;
comp_biconexe[comp_biconexe.size()-1].push_back(s);
for(auto el:g[s])
{
if(lvl[el]==0)
{
dfs2(el);
}
}
}
int main()
{
in>>nrNoduri>>nrMuchii;
int x,y;
for(int i =0; i<nrMuchii; i++)
{
in>>x>>y;
g[x].push_back(y);
g[y].push_back(x);
}
dfs(1,-1,1);
for(auto& per:critice)
{
vector <int> comp_biconexa; //punem in vectorul de int primul si al doilea elem din critice
comp_biconexa.push_back(per.first);
comp_biconexa.push_back(per.second);
comp_biconexe.push_back(comp_biconexa); // punem in vectorul de vector componentele biconexe
}
eliminare_muchii_critice();
for(int i=1; i<=nrNoduri; i++)
{
lvl[i]=0; //resetare vector lvl folosit ca viz
}
for(int i=1;i<=nrNoduri; i++)
{
if(lvl[i]==0)
{
comp_biconexe.push_back(vector<int> ()); //pune vector gol in vectorul mare
dfs2(i);
if(comp_biconexe[comp_biconexe.size()-1].size()==1) //ultimul elem din comp_biconexe
{
comp_biconexe.pop_back(); //sterge elem cu un singur nod
}
}
}
out<<comp_biconexe.size()<<'\n';
for(auto& el:comp_biconexe)
{
for(auto& elem:el)
{
out<<elem<<' ';
}
out<<'\n';
}
return 0;
}