Cod sursa(job #2412875)

Utilizator Andrei-27Arhire Andrei Andrei-27 Data 22 aprilie 2019 17:02:06
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.67 kb
#include <bits/stdc++.h>
#define mp make_pair
using namespace std;
const int NR = 100005 ;
ofstream out ("biconex.out") ;
vector < int > v [ NR ] ;
vector < pair < int , int > > st ;
int n , m , lvl [ NR ] , lowest [ NR ] ;
vector < vector < int > > ans ;
void make_cb ( int x , int y )  {
    vector < int > c;
    int cx , cy ;
    do  {
        cx = st.back().first ;
        cy = st.back().second ;
        st.pop_back() ;
        c.push_back( cx ) , c.push_back( cy ) ;
    }while ( !( cx == x && cy == y ) ) ;
    ans.push_back( c ) ;
}
void dfs ( int nod , int father )   {
    vector < int > :: iterator it ;
    lowest [ nod ] = lvl [ nod ] ;
    for ( it = v [ nod ].begin() ; it != v [ nod ].end() ; ++ it )  {
        if ( *it == father )    continue ;
        if ( !lvl [ *it ] ) {
            lvl [ *it ] = lvl [ nod ] + 1 ;
            st.push_back( mp ( nod , *it ) ) ;
            dfs( *it , nod ) ;
            lowest [ nod ] = min ( lowest [ nod ] , lowest [ *it ] ) ;
            if ( lowest [ *it ] >= lvl [ nod ] )    make_cb ( nod , *it ) ;
        }   else    {
            lowest [ nod ] = min ( lowest [ nod ] , lvl [ *it ] ) ;
        }
    }

}


class InParser {
private:
	FILE *fin;
	char *buff;
	int sp;

	char read_ch() {
		++sp;
		if (sp == 4096) {
			sp = 0;
			fread(buff, 1, 4096, fin);
		}
		return buff[sp];
	}

public:
	InParser(const char* nume) {
		fin = fopen(nume, "r");
		buff = new char[4096]();
		sp = 4095;
	}

	InParser& operator >> (int &n) {
		char c;
		while (!isdigit(c = read_ch()) && c != '-');
		int sgn = 1;
		if (c == '-') {
			n = 0;
			sgn = -1;
		} else {
			n = c - '0';
		}
		while (isdigit(c = read_ch())) {
			n = 10 * n + c - '0';
		}
		n *= sgn;
		return *this;
	}

	InParser& operator >> (long long &n) {
		char c;
		n = 0;
		while (!isdigit(c = read_ch()) && c != '-');
		long long sgn = 1;
		if (c == '-') {
			n = 0;
			sgn = -1;
		} else {
			n = c - '0';
		}
		while (isdigit(c = read_ch())) {
			n = 10 * n + c - '0';
		}
		n *= sgn;
		return *this;
	}
};

int main()  {
    InParser in ("biconex.in") ;
   int x , y , a , b ;
   in >> n >> m ;
   lvl [ 1 ] = 1 ;
   while ( m -- )   {
    in >> x >> y ;
    v [ x ].push_back ( y ) ;
    v [ y ].push_back ( x ) ;
   }
   dfs( 1 , 0 ) ;
   a = ans.size() ;
   out << a << '\n' ;
    for ( size_t i = 0 ; i < a ; ++ i , out << '\n' )   {
        sort( ans [ i ].begin() , ans[ i ].end() ) ;
        ans [ i ].erase( unique( ans [ i ].begin() , ans [ i ].end()) , ans [ i ].end() ) ;
        b = ans [ i ].size() ;
        for ( size_t j = 0 ; j < b ; ++ j ) out << ans[ i ][ j ] << ' ' ;
    }
}