Pagini recente » Monitorul de evaluare | Monitorul de evaluare | Borderou de evaluare (job #3338017) | Autentificare | Cod sursa (job #3337070)
#include <fstream>
#include <vector>
#include <stack>
#include <set>
using namespace std;
ifstream f("biconex.in");
ofstream g("biconex.out");
int n,m,x,y;
vector<vector<int>> adj;
vector<int> visited;
vector<int> nivel;
vector<int> nivel_min;
stack<pair<int,int>> st;
int idxComp = 0;
vector<vector<int>> comp_biconexa;
void bison_biconex(const pair<int,int>& pereche){
set<int> noduri;
while(true){
auto [u,v] = st.top();
st.pop();
noduri.insert(u);
noduri.insert(v);
if((pereche.first == u && pereche.second == v) || (pereche.first == v && pereche.second == u)){
break;
}
}
vector<int> componenta(noduri.begin(), noduri.end());
comp_biconexa.push_back(componenta);
}
void as_hali_salam_dar_nam(int nod){
visited[nod] = 1;
nivel_min[nod] = nivel[nod];
for(auto& neigh: adj[nod]){
if(visited[neigh] == 0){
nivel[neigh] = nivel[nod] + 1;
st.push({nod,neigh});
as_hali_salam_dar_nam(neigh);
nivel_min[nod] = min(nivel_min[neigh], nivel_min[nod]);
if(nivel_min[neigh] >= nivel[nod]){
bison_biconex({nod,neigh});
}
}
else if(visited[neigh] == 1 && nivel[neigh] < nivel[nod] - 1){
nivel_min[nod] = min(nivel[neigh], nivel_min[nod]);
}
}
}
int main(){
f >> n >> m;
adj.resize(n+1, vector<int>());
visited.resize(n+1, 0);
nivel.resize(n+1, 0);
nivel_min.resize(n+1, 0);
for(int i=1; i<=m; i++){
f >> x >> y;
adj[x].push_back(y);
adj[y].push_back(x);
}
nivel[1] = 1;
as_hali_salam_dar_nam(1);
g << comp_biconexa.size() << '\n';
for(int i=0; i< comp_biconexa.size(); i++){
for(auto& kylie_jenner: comp_biconexa[i]){
g << kylie_jenner << " ";
}
g << '\n';
}
return 0;
}