Pagini recente » Cod sursa (job #2679333) | Cod sursa (job #737656) | Cod sursa (job #320446) | Cod sursa (job #16754) | Cod sursa (job #2246191)
#include <fstream>
#include <vector>
#define nmax 100002
using namespace std;
fstream f1("biconex.in", ios::in);
fstream f2("biconex.out", ios::out);
int nrcomp, n, m, niv[nmax], low[nmax];
vector<int> v[nmax], q;
vector<vector<int> > comp;
///low[nod]=min(niv[nod], low["fiu" nod nevizitat], niv["fiu" nod vizitat])
void dfs(int nod, int tata, int nivel){
niv[nod]=low[nod]=nivel;
q.push_back(nod);
for(auto it=v[nod].begin(); it!=v[nod].end(); ++it)
if(*it!=tata){
if(niv[*it]) low[nod]=min(low[nod], niv[*it]);
else {dfs(*it, nod, nivel+1); low[nod]=min(low[nod], low[*it]);}
}
if((nod!=1)&&(low[nod]>=niv[tata])){ //tata este punct de articulatie, pui in noua comp nod, toate nodurile neluate de sub el+ tata
nrcomp++; vector<int> ceva; ceva.clear();
while((!q.empty())&&(q.back()!=nod)){
ceva.push_back(q.back()); q.pop_back();
}
ceva.push_back(q.back()); q.pop_back();
ceva.push_back(tata); /// sau q.back()
comp.push_back(ceva);
}
}
int main(){
int x, y;
f1>>n>>m;
for(int i=1; i<=m; i++){
f1>>x>>y;
v[x].push_back(y);
v[y].push_back(x);
}
dfs(1, -1, 1);
f2<<nrcomp<<"\n";
for(auto it2=comp.begin(); it2!=comp.end() ;++it2){
for(auto it=(*it2).begin(); it!=(*it2).end(); ++it)
f2<<*it<<' ';
f2<<"\n";
}
return 0;
}