Pagini recente » Cod sursa (job #3165874) | Cod sursa (job #2015500) | Cod sursa (job #2393863) | Cod sursa (job #479519) | Cod sursa (job #1964552)
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ifstream in("biconex.in");
ofstream out("biconex.out");
int n,m;
vector<int> L[100005];
int ncomp;
int LOW[100005],DFN[100005];
vector<int> SOL[100005];
stack<int> S;
void read(){
in>>n>>m;
for(int i=1,x,y;i<=m;i++){
in>>x>>y;
L[x].push_back(y);
L[y].push_back(x);
}
}
void dfs(int nod){
S.push(nod);
for(auto x : L[nod]){
if(!LOW[x]){
int c=S.size();
LOW[x]=DFN[x]=DFN[nod]+1;
dfs(x);
LOW[nod]=min(LOW[nod],LOW[x]);
if(LOW[x]>=DFN[nod]){ //! => nod= punct de articulatie
ncomp++;
while(S.size()>c){
SOL[ncomp].push_back(S.top());
S.pop();
}
SOL[ncomp].push_back(nod);
}
}
else LOW[nod]=min(LOW[nod],DFN[x]);
}
}
void solve(){
LOW[1]=DFN[1]=1;
dfs(1);
out<<ncomp<<"\n";
for(int i=1;i<=ncomp;i++){
for(auto x : SOL[i]){
out<<x<<" ";
}
out<<"\n";
}
}
int main(){
read();
solve();
return 0;
}