Cod sursa(job #1670552)

Utilizator daniel.grosuDaniel Grosu daniel.grosu Data 31 martie 2016 20:35:24
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.43 kb
// Template v2
#define pb push_back
#define mp make_pair
#define first x
#define second y
#define l(x) x<<1
#define r(x) x<<1 | 1
#define lsb(x) x & -x
#include<bits/stdc++.h>
#include <bitset>
using namespace std;
 
typedef long long LL;
typedef long double LD;
typedef vector<int> VI;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
typedef pair<double, double> PKK;
// primes less than 100
const int PRIM[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97};
const int CMAX = 10005;
const int MOD = 666013;
const int NMAX = 100010;
const short INF16 = 32000;
const int INF = 1e9 + 10;
const LL INF64 = LL(1e18);
const LD EPS = 1e-9, PI = acos(-1.0);

vector<PII> G[NMAX];
VI C[NMAX];
bool bridge[2*NMAX];
bool viz[NMAX];
int lvl[NMAX], low[NMAX];
int n,m,t,c;

void dfs(int v, int p)
{
    lvl[v]=low[v]=++t;
    viz[v]=true;
    
    for(auto e : G[v])
    {
        int w=e.x;
        if(w==p)
            continue;
            
        if(viz[w])
            low[v]=min(low[v], lvl[w]);
        else
        {
            dfs(w, v);
            low[v]=min(low[v], low[w]);
            
            if(low[w] > lvl[v])
                bridge[e.y]=true;
        }
    }
}

void collect(int v)
{
    C[c].pb(v);
    viz[v]=true;
    for(auto e : G[v])
    {
        int w=e.x;
        if(!bridge[e.y] && !viz[w])
            collect(w);
    }
}

int x,y;
void read()
{
    cin>>n>>m;
    for(int i=1; i<=m; ++i)
    {
        cin>>x>>y;
        G[x].pb(mp(y, i));
        G[y].pb(mp(x, i));
    }
    
    dfs(1, 0);
    
    memset(viz, 0, sizeof(viz));
    
    for(int i=1; i<=n; ++i)
        if(!viz[i]){
            c++;
            collect(i);
        }
    for(int i=1; i<=n; ++i)
        for(auto e : G[i])
            if(bridge[e.y]){
                bridge[e.y]=false;
                c++;
                C[c].pb(i);
                C[c].pb(e.x);
            }
    for(int i=1; i<=c; ++i)
        if(C[i].size()==1)
            c--;
    
    cout<<c<<" \n";
    for(int i=1; i<=c; ++i){
        if(C[i].size()==1)
            c++;
        else{
            for(int k=0; k<C[i].size(); ++k)
                cout<<C[i][k]<<" ";
        
            cout<<"\n";
        }
    }
}
 
int main(){
    assert(freopen("biconex.in", "rt", stdin));
    assert(freopen("biconex.out", "wt", stdout));
    
    cin.tie(0);
    ios_base::sync_with_stdio(0);
    cout << setprecision(16) << fixed;
    read();
     
    return 0;
}