Cod sursa(job #2025934)

Utilizator bogdan10bosBogdan Sitaru bogdan10bos Data 23 septembrie 2017 14:33:38
Problema Componente biconexe Scor 90
Compilator cpp Status done
Runda Arhiva educationala Marime 2.26 kb
#include <bits/stdc++.h>

using namespace std;

#define FILE_IO

typedef pair<int, int> pii;

int N, M;
int h[100005], grd[100005], low[100005];
vector<pii> edges;
vector<int> edg[100005];
bool art[100005], done[100005];

vector<int> cmp;
vector< vector<int> > bcc;

int DFS(int nod, int fth)
{
    h[nod] = h[fth] + 1;
    low[nod] = h[nod];
    int sons = 0;
    for(auto nxt: edg[nod])
    {
        if(nxt == fth)  continue;
        if(h[nxt] != 0) { low[nod] = min(low[nod], h[nxt]); continue; }
        DFS(nxt, nod);
        if(low[nxt] >= h[nod])  art[nod] = 1;
        low[nod] = min(low[nod], low[nxt]);
        sons++;
    }
    return sons;
}

bool bridge(int x, int y)
{
    if(h[x] > h[y]) swap(x, y);
    if(low[y] > h[x])   return true;
    return false;
}

void DFS2(int nod)
{
    if(done[nod])   return;
    done[nod] = 1;
    cmp.push_back(nod);
    for(auto nxt: edg[nod])
        DFS2(nxt);
}

int main()
{
    #ifdef FILE_IO
    freopen("biconex.in", "r", stdin);
    freopen("biconex.out", "w", stdout);
    #endif

    scanf("%d%d", &N, &M);
    for(int i = 1; i <= M; i++)
    {
        int x, y;
        scanf("%d%d", &x, &y);
        edg[x].push_back(y);
        edg[y].push_back(x);
        edges.push_back({x, y});
        grd[x]++, grd[y]++;
    }

    int sns = DFS(1, 0);
    if(sns > 1) art[1] = 1;

    for(auto e: edges)
        if( bridge(e.first, e.second) )
        {
            for(auto it = edg[e.first].begin(); it != edg[e.first].end(); it++)
                if( (*it) == e.second ) { edg[e.first].erase(it); break; }
            for(auto it = edg[e.second].begin(); it != edg[e.second].end(); it++)
                if( (*it) == e.first ) { edg[e.second].erase(it); break; }

            cmp.clear();
            cmp.push_back(e.first);
            cmp.push_back(e.second);
            bcc.push_back(cmp);
        }

    for(int i = 1; i <= N; i++)
        if(!done[i] && !edg[i].empty())
        {
            cmp.clear();
            DFS2(i);
            bcc.push_back(cmp);
        }

    printf("%d\n", bcc.size());
    for(auto v: bcc)
    {
        sort(begin(v), end(v));
        for(auto x: v)  printf("%d ", x);
        printf("\n");
    }

    return 0;
}