Pagini recente » Cod sursa (job #165192) | Cod sursa (job #1776861) | Cod sursa (job #3003334) | Cod sursa (job #2471942) | Cod sursa (job #1649280)
#include <fstream>
#include <stack>
#include <set>
#include <vector>
#define DMAX 200005
#define DVFM 100005
using namespace std;
int nr_bic, n, m, a, b, index;
struct muchie {
int c1, c2;
} temp;
stack <muchie> st;
set <int> comp_bic[DMAX];
set <int>::iterator it;
vector <int> edges[DVFM];
int idx[DVFM], lwl[DVFM], dad[DVFM];
void gasit(int a, int b){
nr_bic++;
temp = st.top();
while(temp.c1 != a || temp.c2 != b){
comp_bic[nr_bic].insert(temp.c1);
comp_bic[nr_bic].insert(temp.c2);
st.pop();
temp = st.top();
}
comp_bic[nr_bic].insert(temp.c1);
comp_bic[nr_bic].insert(temp.c2);
st.pop();
}
void dfs(int vf){
int vecin;
idx[vf] = ++index;
lwl[vf] = idx[vf];
for(int i = 0; i < edges[vf].size(); ++i){
vecin = edges[vf][i];
if(!idx[vecin]){
dad[vecin] = vf;
temp.c1 = vf;
temp.c2 = vecin;
st.push(temp);
dfs(vecin);
lwl[vf] = (lwl[vf] > lwl[vecin]) ? lwl[vecin] : lwl[vf];
if(lwl[vecin] >= idx[vf]){
gasit(vf, vecin);
}
}
if(dad[vf] != vecin){
lwl[vf] = (lwl[vf] > idx[vecin]) ? idx[vecin] : lwl[vf];
}
}
}
int main()
{
ifstream in("biconex.in");
ofstream out("biconex.out");
in>>n>>m;
for(int i = 1; i <= m; ++i){
in>>a>>b;
edges[a].push_back(b);
edges[b].push_back(a);
}
dfs(1);
out<<nr_bic<<"\n";
for(int i = 1; i <= nr_bic; ++i){
for(it = comp_bic[i].begin(); it != comp_bic[i].end(); it++){
out<<(*it)<<" ";
}
out<<"\n";
}
in.close();
out.close();
return 0;
}