Pagini recente » Cod sursa (job #3278356) | Cod sursa (job #469034) | Cod sursa (job #508378) | Cod sursa (job #397999) | Cod sursa (job #2599587)
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
const int MAXN = 200001;
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 afis(){
for(int i = 1; i <= n; i++)
cout<<minim[i]<<" ";
cout<<endl;
}
void dfs(int nod,int tata = 0){
viz[nod] = true;
// cout<<"Fata"<<"\n";
// afis();
for(auto vecin : graf[nod]){
if(viz[vecin] && vecin != tata && inaltime[vecin] < inaltime[nod]){
stiva.emplace_back(nod,vecin);
/// ma duc sus pe graf
minim[nod] = min(minim[nod],minim[vecin]);
}else if(!viz[vecin]){
inaltime[vecin] = ++cnt;
minim[vecin] = inaltime[vecin];
stiva.emplace_back(nod,vecin);
dfs(vecin,nod);
}
}
if(tata != 0 && minim[nod] >= inaltime[tata]){
// cout<<tata<<" "<<nod<<"tata nod\n";
// for(auto muchie : stiva)
// cout<<muchie.first<<" "<<muchie.second<<"\n";
biconexa(tata,nod);
}
if(minim[nod] < minim[tata])
minim[tata] = minim[nod];
// cout<<"Inapoi"<<"\n";
// afis();
}
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);
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;
}