Pagini recente » Istoria paginii runda/fdgf.g | Cod sursa (job #694282) | Istoria paginii runda/easylasmdp/clasament | Cod sursa (job #1043508) | Cod sursa (job #1156689)
#include <fstream>
#include <vector>
#include <stack>
#define nmax 100005
using namespace std;
vector<int> gf[nmax], sol[nmax];
int n, m, H[nmax], nv[nmax], r;
stack<pair<int,int> > st;
int viz[nmax];
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){
H[nod] = nv[nod] = nr;
for(unsigned 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 (H[nod] > H[ gf[nod][i] ])
H[nod] = H[ gf[nod][i] ];
if (H[ gf[nod][i] ] >= nv[nod]){
r++;
int x, y;
for(int i=1; i<=n; i++) viz[i] = 0;
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;
}while(x != nod || y != gf[nod][i]);
}
}else if (H[nod] > nv[ gf[nod][i] ])
H[nod] = nv[ gf[nod][i] ];
}
}
void scrie(){
g<<r<<"\n";
for(int i=1; i<=r; i++){
for(unsigned int j=0; j < sol[i].size(); j++)
g<<sol[i][j]<<" ";
g<<"\n";
}
}
int main(){
citeste();
dfs(1,0,0);
scrie();
f.close();
g.close();
return 0;
}