Pagini recente » Cod sursa (job #3312405) | Cod sursa (job #3314433) | Cod sursa (job #3310220) | Cod sursa (job #2680980) | Cod sursa (job #3334158)
#include <fstream>
#include <vector>
#include <stack>
#include <set>
using namespace std;
ifstream f("biconex.in");
ofstream g("biconex.out");
const int INF = 1e8;
int n,m,x,y;
vector<vector<int>> adj;
vector<int> visited;
vector<int> nivel;
vector<int> niv_min;
stack<pair<int,int>> st;
vector<vector<int>> rez;
void critic(int nod,int tata){
visited[nod] = 1;
niv_min[nod] = nivel[nod];
for(auto& neigh: adj[nod]){
if(visited[neigh] == 0){
st.push({nod,neigh});
nivel[neigh] = nivel[nod] + 1;
critic(neigh,nod);
niv_min[nod] = min(niv_min[neigh], niv_min[nod]);
if(niv_min[neigh] >= nivel[nod]){ //critical node condition (>=) | critical edge condition (>)
set<int> componenta_conexa;
while(true){
pair<int,int> muchie = st.top();
st.pop();
componenta_conexa.insert(muchie.first);
componenta_conexa.insert(muchie.second);
if(muchie.first == nod && muchie.second == neigh)
break;
if(muchie.first == neigh && muchie.second == nod)
break;
}
vector<int> comp(componenta_conexa.begin(), componenta_conexa.end());
rez.push_back(comp);
}
}
else{
if(tata!=neigh && nivel[neigh] < nivel[nod]){
st.push({nod,neigh});
niv_min[nod] = min(niv_min[nod], nivel[neigh]);
}
}
}
}
int main(){
f >> n >> m;
adj.resize(n+1);
visited.assign(n+1, 0);
nivel.assign(n+1, 0);
niv_min.assign(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;
critic(1,-1);
g << rez.size() << '\n';
for(int i=0; i<rez.size(); i++){
int n=rez[i].size();
for(int j=0; j<n; j++){
g << rez[i][j] << " ";
}
g << '\n';
}
return 0;
}