Pagini recente » Cod sursa (job #1718691) | Cod sursa (job #1128187) | Cod sursa (job #2878401) | Cod sursa (job #140015) | Cod sursa (job #2599596)
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
const int MAXN = 1e5 + 5;
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;
for(int i = 0; i < graf[nod].size(); i++){
int vecin = graf[nod][i];
if(viz[vecin] && vecin != tata && inaltime[vecin] < inaltime[nod]){
stiva.push_back({nod,vecin});
/// ma duc sus pe graf
minim[nod] = min(minim[nod],inaltime[vecin]);
}else if(!viz[vecin]){
inaltime[vecin] = ++cnt;
minim[vecin] = inaltime[vecin];
stiva.push_back(make_pair(nod,vecin));
dfs(vecin,nod);
}
}
if(tata != 0 && minim[nod] >= inaltime[tata]){
biconexa(tata,nod);
}
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);
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;
}