Cod sursa(job #1074576)

Utilizator Adrian1997Radulescu Adrian Adrian1997 Data 7 ianuarie 2014 19:25:00
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.78 kb
#include <fstream>
#include <vector>
#include <algorithm>
#include <stack>
#define minim(a,b) (a<b?a:b)
using namespace std;
ifstream f("biconex.in");
ofstream g("biconex.out");
int n,m,niv,CB;
int low[100011];
bool viz[100011];

vector<int> L[100011],c[100011];
stack<pair<int,int> > S;

void dfs(int nod,int niv,int tata){
    int x,y;
    pair<int,int> p;
    low[nod]=niv;
    viz[nod]=true;
    for(register int i=0;i<L[nod].size();i++){
        if(L[nod][i]==tata)
            continue;
        if(!viz[L[nod][i]]){
            //pun in stiva muchua nod,L[nod][i]
            S.push(make_pair(nod,L[nod][i]));
            dfs(L[nod][i],niv+1,nod);


            if (low[ L[nod][i] ] >= niv) {
                // plecarea pe muchia nod,L[nod][i] a produs o CB
                // scot toate muchiile din stiva pana la aceasta inclusiv
                // si toate muchiile sintre nodurile ce apar la muchii din
                // stiva sunt o CB
                CB++;
                x=nod,y=L[nod][i];
                do{
                    p=S.top();
                    c[CB].push_back(p.second);
                    c[CB].push_back(p.first);
                    S.pop();
                }while(x!=p.first || y!=p.second);
            }


        }
        low[nod]=minim(low[nod],low[L[nod][i]]);

    }
}

int main(void){
    register int i,j,x,y;

    f>>n>>m;
    for(i=1;i<=m;i++){
        f>>x>>y;
        L[x].push_back(y);
        L[y].push_back(x);
    }
    dfs(1,1,0);

    g<<CB<<"\n";
    for(i=1;i<=CB;i++){
        sort(c[i].begin(),c[i].end());
        g<<c[i][0]<<" ";
        for(j=1;j<c[i].size();j++)
            if(c[i][j]!=c[i][j-1]) g<<c[i][j]<<" ";
        g<<"\n";
    }
    f.close();
    g.close();
    return 0;
}