Pagini recente » Cod sursa (job #1834212) | Cod sursa (job #2414635) | Cod sursa (job #2954561) | Cod sursa (job #2542732) | Cod sursa (job #2544680)
#include<iostream>
#include<fstream>
#include<vector>
#include<stack>
#define NMAX 100010
using namespace std;
ofstream o("biconex.out");
int n,ids[NMAX],low[NMAX],id=0,cbc=0;
bool viz[NMAX],art[NMAX];
stack <pair<int,int> > S;
vector <pair<int,int> > m;
vector <int> v[NMAX],com[NMAX];
void citire(){
ifstream f("biconex.in");
int i,m,y,x; f>>n>>m;
for(i=1;i<=m;i++){
f>>x>>y;
v[x].push_back(y);
v[y].push_back(x);
}
f.close();
}
void dfs(int k,int tata){
ids[k]=low[k]=++id;
int i,nv;
for(i=0;i<v[k].size();i++){
nv=v[k][i];
if(tata==nv) continue;
if(!ids[nv]){
S.push(make_pair(k,nv));
dfs(nv,k);
low[k]=min(low[k],low[nv]);
if(ids[k]<=low[nv]){
cbc++; int m1,m2;
do{
m1=S.top().first; m2=S.top().second;
S.pop();
com[cbc].push_back(m1); com[cbc].push_back(m2);
}while(m1!=k||m2!=nv);
}
}
else low[k]=min(low[k],low[nv]);
}
}
void articulatie(){
int i,j;
for(i=1;i<=n;i++)
if(!viz[i]){
dfs(i,0);
}
o<<cbc<<'\n';
for(i=1;i<=cbc;i++)
{
for(j=0;j<com[i].size();j++)
o<<com[i][j]<<" ";
o<<'\n';
}
o.close();
}
int main(){
citire();
articulatie();
}