Pagini recente » Cod sursa (job #924372) | Cod sursa (job #2735479) | Cod sursa (job #2884139) | Cod sursa (job #131398) | Cod sursa (job #2595233)
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
const int MAXN = 100001;
using namespace std;
ifstream in("biconex.in");
ofstream out("biconex.out");
vector<int>graf[MAXN];
vector<pair<int,int>>stiva;
int n,m,inaltime[MAXN],minim[MAXN];
int nr_comp,cnt = 1;
vector<int>componente[MAXN];
bool viz[MAXN];
void biconexa(int x,int y){
nr_comp++;
while(stiva.back() != make_pair(x,y)){
int nod1 = stiva.back().first,nod2 = stiva.back().second;
componente[nr_comp].push_back(nod1);
componente[nr_comp].push_back(nod2);
stiva.pop_back();
}
componente[nr_comp].push_back(x);
componente[nr_comp].push_back(y);
stiva.pop_back();
}
void dfs(int nod,int tata = 0){
viz[nod] = true;
for(auto vecin : graf[nod]){
if(vecin != tata && inaltime[vecin] < inaltime[nod])
stiva.emplace_back(nod,vecin);
if(viz[vecin] && vecin != tata && inaltime[vecin] < inaltime[nod]){
/// ma duc sus pe graf
minim[nod] = minim[vecin];
}else if(!viz[vecin]){
inaltime[vecin] = ++cnt;
minim[vecin] = inaltime[vecin];
dfs(vecin,nod);
}
}
if(minim[nod] >= minim[tata] && tata){
// cout<<tata<<" "<<nod<<endl;
// cout<<"stiva : "<<"\n";
// for(int i = stiva.size() - 1; i >= 0; i--)
// cout<<stiva[i].first<<" "<<stiva[i].second<<"\n";
// cout<<"======="<<"\n";
biconexa(tata,nod);
}
//cout<<tata<<" "<<nod<<" "<<minim[tata]<<" "<<minim[nod]<<endl;
if(minim[nod] < minim[tata])
minim[tata] = minim[nod];
}
int main()
{
in>>n>>m;
for(int i = 1; i <= m; i++){
int x,y;
in>>x>>y;
graf[x].push_back(y);
graf[y].push_back(x);
}
inaltime[1] = minim[1] = 1;
dfs(1);
// for(int i = 1; i <= n; i++)
// cout<<minim[i]<<" ";
out<<nr_comp<<"\n";
for(int i = 1; i <= nr_comp; i++){
sort(componente[i].begin(),componente[i].end());
componente[i].erase(unique(componente[i].begin(),componente[i].end()),componente[i].end());
for(auto nod : componente[i])
out<<nod<<" ";
out<<"\n";
}
return 0;
}