Pagini recente » Cod sursa (job #1097722) | Cod sursa (job #3220886) | Cod sursa (job #1977787) | Cod sursa (job #1403778) | Cod sursa (job #629198)
Cod sursa(job #629198)
#include <fstream>
#include <vector>
using namespace std;
ifstream in("biconex.in");
ofstream out("biconex.out");
const int N=100001;
const int M=200001;
struct muchie{
int a,b;
}ordinedf[M];
vector <int> muchii[N],solutii[N];
int nivm[N],niv[N];// nivelul mminim la care se poate ajunge pe un drum in jos si apoi pe muchie de intoarecere. este initializat cu nivelului sau; nivelul N
int n,m,nrmuchiidf,nrbiconexe;//numarul de muchii de arbore parcurse deja de df
bool viz[N];//vectorul de vizitat asociat df-ului
int minimim(int a,int b){
return a<b;
}
void citiremuchii(){
int i,a,b;
for(i=1;i<=m;i++){
in>>a>>b;
muchii[a].push_back(b);
muchii[b].push_back(a);
}
}
void update(int x,int y){
nrbiconexe++;
while(ordinedf[nrmuchiidf].a!=x && ordinedf[nrmuchiidf].b!=y){
solutii[nrbiconexe].push_back(ordinedf[nrmuchiidf].b);
nrmuchiidf--;
}
solutii[nrbiconexe].push_back(ordinedf[nrmuchiidf].b);
solutii[nrbiconexe].push_back(ordinedf[nrmuchiidf].a);
nrmuchiidf--;
}
void df(int x,int parinte){
int i,y;
viz[x]=true;
nivm[x]=niv[parinte]+1;
niv[x]=niv[parinte]+1;
for(i=0;i<muchii[x].size();i++){
y=muchii[x][i];
if(!viz[y]){
nrmuchiidf++;
ordinedf[nrmuchiidf].a=x;
ordinedf[nrmuchiidf].b=y;
df(y,x);
if(niv[x]<=nivm[y]){
update(x,y);
}
nivm[x]=min(nivm[x],nivm[y]);
continue;
}
else{
if(y!=parinte)
nivm[x]=min(nivm[x],niv[y]);
}
}
}
void solve(){
int i;
for(i=1;i<=n;i++){
if(!viz[i]){
df(i,1);
}
}
}
int main(){
int i,j;
in>>n>>m;
citiremuchii();
solve();
out<<nrbiconexe<<"\n";
for(i=1;i<=n;i++){
for(j=solutii[i].size()-1;j>=0;j--){
out<<solutii[i][j]<<" ";
}
out<<"\n";
}
return 0;
}