Cod sursa(job #625687)

Utilizator valentin.harsanValentin Harsan valentin.harsan Data 25 octombrie 2011 11:29:09
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.49 kb
#include<iostream>
#include<fstream>
#include<vector>
#include<algorithm>
#define N 200001
using namespace std;

ifstream in("biconex.in");
ofstream out("biconex.out");

int n,m,nivel[N],nrc,parint[N],st1[N],st2[N],c[N],u;
vector<int> g[N],v[N];
bool vizitat[N],ver[N];

void add(int a,int b) {
    int x,y;

    ++nrc;
    do {
        x=st1[u];
        y=st2[u--];

        v[nrc].push_back(y);
    } while(x!=a || y!=b);

    v[nrc].push_back(x);
}

void c_bi(int nod, int parinte) {

   vizitat[nod]=true;
   c[nod]=nivel[nod]=nivel[parinte]+1;
   parint[nod]=parinte;

   vector<int>::iterator it;
   int aux;

   for(it=g[nod].begin();it!=g[nod].end();++it) if((*it)!=parinte) {

        if(!vizitat[*it]) {
            st1[++u]=nod;
            st2[u]=*it;

            c_bi(*it,nod);

            if(c[*it]<c[nod])
              c[nod]=c[*it];
            if(c[*it]>=nivel[nod])
              add(nod,*it);
        }
        else if(*it!=parinte && c[*it]<c[nod])
           c[nod]=c[*it];
    }

}

int main() {
    int i,a,b,aux,j,vver;
	vector<int>::iterator it;

    in >> n >> m;

    for(i=1;i<=m;++i) {
        in >> a >> b;

        g[a].push_back(b);
        g[b].push_back(a);
    }

    c_bi(1,0);

    out << nrc << "\n";

    for(i=1;i<=nrc;++i) {

        sort(&v[i][0],&v[i][v[i].size()]);

        for(it=v[i].begin();it!=v[i].end();++it)
            out << *it << " ";

        out << "\n";
    }

    return 0;
}