Cod sursa(job #1076026)

Utilizator Adrian1997Radulescu Adrian Adrian1997 Data 9 ianuarie 2014 20:24:46
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.48 kb
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>
#define minim(a,b) (a<b?a:b)
using namespace std;
ifstream f("biconex.in");
ofstream g("biconex.out");
int n,m,nr;
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;
    viz[nod]=true;
    low[nod]=niv;
    for(register int i=0;i<L[nod].size();i++){
        if(L[nod][i]==tata)
            continue;
        if(!viz[L[nod][i]]){
            S.push(make_pair(nod,L[nod][i]));
            dfs(L[nod][i],niv+1,nod);
            if(low[L[nod][i]]>=niv){
                nr++;
                x=nod,y=L[nod][i];
                do{
                    p=S.top(),S.pop();
                    C[nr].push_back(p.second);
                    C[nr].push_back(p.first);
                }
                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<<nr<<"\n";
    for(i=1;i<=nr;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;
}