Pagini recente » Cod sursa (job #153105) | Cod sursa (job #1320257) | Cod sursa (job #2615820) | Cod sursa (job #2175477) | Cod sursa (job #852647)
Cod sursa(job #852647)
#include<fstream>
#include<vector>
#include<stack>
#include<algorithm>
using namespace std;
int n, m, index,
tata[100005],
intoarcere[100005],
DFlevel[100005];
vector <int> graph[100005];
stack <int> stiva; // ordinea nodurilor din df
// stack <int> currentStiva
vector < vector <int> > sol;
void df(int nod){
int urm;
vector <int> currentStiva;
stiva.push(nod);
++index; // la al catelea nod suntem
intoarcere[nod] = index;
DFlevel[nod] = index;
for (int i = 0; i < (int)graph[nod].size(); ++i){
urm = graph[nod][i];
if (!DFlevel[urm]) { // adica dc inca nu am facut df din nodul urm
tata[urm] = nod;
df(urm);
// dc are drum in jos care se intoarce mai sus decat nod
intoarcere[nod] = intoarcere[nod] < intoarcere[urm] ? intoarcere[nod] : intoarcere[urm];
}
else if (tata[nod] != urm)
intoarcere[nod] = intoarcere[nod] < intoarcere[urm] ? intoarcere[nod] : intoarcere[urm];
}//end of for
if (intoarcere[nod] == DFlevel[nod]){ // dc se intoarce in el insusi sau nu are muchie de intoarcere
do{
urm = stiva.top();
stiva.pop();
currentStiva.push_back(urm);
}while (nod != urm); // stiva ajunge sa contina toate nodurile (in ordine descrescatoare)
if (currentStiva.size() > 1) // adica daca a scos mai mult decat un nod
sol.push_back(currentStiva);
if (tata[nod]){ //pune articulatia si tatal dc nod nu e radacina (capacul unei comp b) - radacina e pusa in do while la final
currentStiva.clear();
currentStiva.push_back(nod);
currentStiva.push_back(tata[nod]);
sol.push_back(currentStiva); // in sol generata, ultimul nod coincide cu primul nod al urmatoarei solutii (cand ordinea e descrescatoare)
}
}//end of if
}//end of DF
int main(){
ifstream f("biconex.in");
ofstream g("biconex.out");
int x, y, i;
f >> n >> m;
for (i = 0; i < m; ++i){
f >> x >> y;
graph[x].push_back(y);
graph[y].push_back(x);
}
for (i = 1; i <= n ; ++i) if (!DFlevel[i]) df(i);
g << sol.size() << "\n";
for (i = 0; i < (int)sol.size(); ++i){
for (int j = 0; j < (int)sol[i].size(); ++j)
g << sol[i][j] << " ";
g << "\n";
}
}