Cod sursa(job #625408)

Utilizator valentin.harsanValentin Harsan valentin.harsan Data 24 octombrie 2011 16:19:50
Problema Componente biconexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.66 kb
#include<iostream>
#include<fstream>
#include<vector>
#include<algorithm>
#define N 100001
using namespace std;

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

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

void scrie(int nod, int parinte) {

    v[++nrc].push_back(nod);

    while(nod!=parinte) {
        nod=parint[nod];

        v[nrc].push_back(nod);
    }

}

void c_bi(int nod, int parinte, int niv, int &niv_min) {

    if(vizitat[nod])
        niv_min=nivel[nod];
    else {

        vizitat[nod]=true;
        nivel[nod]=niv_min=niv;
        parint[nod]=parinte;

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

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

            c_bi(*it,nod,niv+1,aux);
			
            if(niv<=aux)
                scrie(*it,nod);
			
			if(aux<niv_min)
				niv_min=aux;

        }

    }

}

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,1,aux);
	
	for(i=1;i<=nrc;++i)
		sort(&v[i][0],&v[i][v[i].size()]);
	
	for(i=1;i<nrc;++i) if(v[i].size()<v[i+1].size()) {
		vver=0;
		
		for(j=0;j!=v[i].size();++j)
			if(v[i][j]!=v[i+1][j])
				vver=1;
		
		if(vver==0) {
			--nrc;
			ver[i]=true;
		}
		
	}

    out << nrc << "\n";

    for(i=1;i<=nrc;++i) {
		
		if(ver[i]) {
			++nrc;
			continue;
		}

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

        out << "\n";
    }

    return 0;
}