Cod sursa(job #852647)

Utilizator yamahaFMI Maria Stoica yamaha Data 11 ianuarie 2013 15:41:28
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.49 kb
#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";
    }
}