Pagini recente » Cod sursa (job #646760) | Cod sursa (job #1822661) | Cod sursa (job #1821897) | Cod sursa (job #783562) | Cod sursa (job #671159)
Cod sursa(job #671159)
#include <fstream>
#include <vector>
#include <stack>
#include <set>
#define nmax 100005
using namespace std;
vector<int> gf[nmax];
int n, m, L[nmax], nv[nmax], r;
stack<pair<int,int> > st;
int viz[nmax];
set<int> sol[nmax];
int x, y;
ifstream f("biconex.in");
ofstream g("biconex.out");
void citeste(){
f>>n>>m;
for(int i=1; i<=m; ++i){
int x, y;
f>>x>>y;
gf[x].push_back(y);
gf[y].push_back(x);
}
for(int i=0; i<=n; ++i) nv[i] = -1;
}
void dfs(int nod, int T, int nr){
L[nod] = nv[nod] = nr;
for(int i=0; i<gf[nod].size(); ++i){
if (gf[nod][i] == T) continue;
if (nv[ gf[nod][i] ] == -1){
st.push(make_pair(nod, gf[nod][i]));
dfs(gf[nod][i], nod, nr+1);
if (L[nod] > L[ gf[nod][i] ])
L[nod] = L[ gf[nod][i] ];
if (L[ gf[nod][i] ] >= nv[nod]){
++r;
do{
x = st.top().first;
y = st.top().second;
st.pop();
//if(viz[y]==0) sol[r].push_back(y), viz[y]=1;
//if (viz[x]==0) sol[r].push_back(x), viz[x]=1;
sol[r].insert(x);
sol[r].insert(y);
}while(x != nod || y != gf[nod][i]);
}
}else if (L[nod] > nv[ gf[nod][i] ])
L[nod] = nv[ gf[nod][i] ];
}
}
void scrie(){
g<<r<<"\n";
for(int i=1; i<=r; ++i){
for(set<int>::iterator it = sol[i].begin(); it != sol[i].end(); ++it)
g<<*it<<" ";
g<<"\n";
}
}
int main(){
citeste();
dfs(1,0,0);
scrie();
f.close();
g.close();
return 0;
}