Pagini recente » Cod sursa (job #1411693) | Cod sursa (job #480071) | Cod sursa (job #3168337) | Cod sursa (job #2575862) | Cod sursa (job #1003951)
#include<iostream>
#include<fstream>
#include<vector>
#include<stack>
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
struct node {
bool vizitat;
int mini;
int grad;
vector<int> vecini;
};
struct cuplu {
int a;
int b;
};
int n, m, i, ii, a, b, s1, s2;
node nodes[100001];
cuplu muchie;
stack<cuplu> stiva;
vector<int> sol;
vector<vector<int> > solutie;
void dfs(int x) {
int j;
int l = nodes[x].vecini.size();
for(j = 0; j < l; j++) {
int vecin = nodes[x].vecini[j];
if(nodes[vecin].vizitat == false) {
muchie.a = x;
muchie.b = vecin;
stiva.push(muchie);
nodes[vecin].vizitat = true;
nodes[vecin].grad = nodes[vecin].mini = nodes[x].grad + 1;
dfs(vecin);
nodes[x].mini = min(nodes[x].mini, nodes[vecin].mini);
if(nodes[vecin].mini >= nodes[x].grad) {
do {
muchie = stiva.top();
stiva.pop();
sol.push_back(muchie.b);
}while(muchie.a != x);
sol.push_back(muchie.a);
solutie.push_back(sol);
sol.clear();
}
}
else {
if(nodes[vecin].grad != nodes[x].grad - 1) {
nodes[x].mini = min(nodes[x].mini, nodes[vecin].grad);
}
}
}
}
int main() {
fin >> n >> m;
for(i = 0; i < m; i++) {
fin >> a >> b;
nodes[a].vecini.push_back(b);
nodes[b].vecini.push_back(a);
}
nodes[1].grad = 1;
nodes[1].mini = 1;
nodes[1].vizitat = true;
dfs(1);
s1 = solutie.size();
fout << s1 << '\n';
for(i = 0; i < s1; i++) {
sol = solutie[i];
s2 = sol.size();
for(ii = s2 - 1; ii >= 0; ii--) {
fout << sol[ii] << ' ';
}
fout << '\n';
}
fin.close();
fout.close();
return 0;
}