Pagini recente » Cod sursa (job #742244) | Cod sursa (job #1662883) | Cod sursa (job #2390790) | Cod sursa (job #2753700) | Cod sursa (job #2355411)
#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;
int n,m;
vector<int> graph[NMAX + 5];
int id[NMAX + 5];
int low[NMAX + 5];
int last_id;
pair<int,int> st[MMAX + 5];
int len;
vector< vector<int> > bicco;
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[++len] = {it,nod};
dfs(it,nod);
low[nod] = min(low[nod],low[it]);
if(low[it] >= id[nod]){
vector<int> v;
while(st[len] != make_pair(it,nod)){
v.push_back(st[len].first);
v.push_back(st[len].second);
len--;
}
v.push_back(st[len].first);
v.push_back(st[len].second);
len--;
sort(v.begin(),v.end());
v.resize(unique(v.begin(),v.end()) - v.begin());
bicco.push_back(v);
}
}
}
}
int main(){
fscanf(f,"%d %d",&n,&m);
for(int i = 1;i <= m;i++){
int x,y;
fscanf(f,"%d %d",&x,&y);
graph[x].push_back(y);
graph[y].push_back(x);
}
dfs(1,0);
fprintf(g,"%d\n",(int)bicco.size());
for(auto it:bicco){
for(auto it2:it){
fprintf(g,"%d ",it2);
}
fprintf(g,"\n");
}
return 0;
}