Pagini recente » Monitorul de evaluare | Monitorul de evaluare | Atasamentele paginii Profil Andrei_23 | Monitorul de evaluare | Cod sursa (job #1169882)
#include <fstream>
#include <stack>
#include <vector>
using namespace std;
stack<int> s;
vector<int> v[100005],Sol[100005];
vector<int>::iterator it;
int N,M,cb,x,y,Niv[100005],Low[100005];
inline int minim(int x, int y) {
return x<y ? x : y;
}
void dfs(int nod, int niv) {
Low[nod]=niv;
Niv[nod]=niv;
s.push(nod);
vector<int>::iterator it;
for(it=v[nod].begin();it!=v[nod].end();it++) {
if(Niv[*it]==0) {
dfs(*it,niv+1);
Low[nod]=minim(Low[nod],Low[*it]);
if(Niv[nod]<=Low[*it]) {
cb++;
while(s.top()!=*it) {
Sol[cb].push_back(s.top());
s.pop();
}
Sol[cb].push_back(*it);
s.pop();
Sol[cb].push_back(nod);
}
}
else
Low[nod]=minim(Low[nod],Niv[*it]);
}
}
int main() {
register int i;
ifstream f("biconex.in");
ofstream g("biconex.out");
f>>N>>M;
for(i=1;i<=M;i++) {
f>>x>>y;
v[x].push_back(y);
v[y].push_back(x);
}
for(i=1;i<=N;i++)
if(Niv[i]==0)
dfs(i,1);
g<<cb<<"\n";
for(i=1;i<=cb;i++) {
for(it=Sol[i].begin();it!=Sol[i].end();it++)
g<<*it<<" ";
g<<"\n";
}
return 0;
}