Pagini recente » Cod sursa (job #2586460) | Cod sursa (job #1909227) | Cod sursa (job #2830653) | Cod sursa (job #579817) | Cod sursa (job #2356620)
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
FILE *f = fopen("biconex.in","r");
FILE *g = fopen("biconex.out","w");
const int NMAX = 1e5;
const int MMAX = 2e5;
///0 indexed;
class BiccoSolver{
private:
int n;
vector< vector<int> > graph;
vector<int> id;
vector<int> low;
int last_id;
vector<pair<int,int> > st;
vector<vector<int>> ans;
void dfs(int nod,int tata){
low[nod] = id[nod] = ++last_id;
for(auto it:graph[nod]){
if(it == tata){
continue;
}
if(id[it]){
low[nod] = min(low[nod],id[it]);
}
else{
st.push_back({it,nod});
dfs(it,nod);
low[nod] = min(low[nod],low[it]);
if(low[it] >= id[nod]){
vector<int> v;
while(st.back() != make_pair(it,nod)){
v.push_back(st.back().first);
v.push_back(st.back().second);
st.pop_back();
}
v.push_back(st.back().first);
v.push_back(st.back().second);
st.pop_back();
sort(v.begin(),v.end());
v.resize(unique(v.begin(),v.end()) - v.begin());
ans.push_back(v);
}
}
}
}
public:
BiccoSolver(int n){
this->n = n;
this->graph = vector<vector<int>>(n,vector<int>());
this->id = vector<int>(n,0);
this->low = vector<int>(n,0);
this->last_id = 0;
this->st.clear();
this->ans.clear();
}
void add_edge(int a,int b){
graph[a].push_back(b);
graph[b].push_back(a);
}
vector< vector<int> > solve(){
this->id = vector<int>(n,0);
this->low = vector<int>(n,0);
this->last_id = 0;
this->st.clear();
this->ans.clear();
dfs(0,-1);
return ans;
}
};
int main(){
int n,m;
fscanf(f,"%d %d",&n,&m);
BiccoSolver a(n);
for(int i = 1;i <= m;i++){
int x,y;
fscanf(f,"%d %d",&x,&y);
x--;
y--;
a.add_edge(x,y);
}
vector<vector<int> > bicco = a.solve();
fprintf(g,"%d\n",(int)bicco.size());
for(auto it:bicco){
for(auto it2:it){
fprintf(g,"%d ",it2 + 1);
}
fprintf(g,"\n");
}
return 0;
}