Cod sursa(job #2026005)

Utilizator bogdan10bosBogdan Sitaru bogdan10bos Data 23 septembrie 2017 16:01:34
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.72 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];
pii edges[200005];
vector<int> edg[100005];
bool art[100005], done[100005];

vector< vector<int> > bcc;
stack<int> stv;

int DFS(int nod, int fth)
{
    h[nod] = h[fth] + 1;
    low[nod] = h[nod];
    int sons = 0;
    for(auto e: edg[nod])
    {
        int nxt = nod ^ edges[e].first ^ edges[e].second;
        if(nxt == fth)  continue;
        if(h[nxt] != 0) { low[nod] = min(low[nod], h[nxt]); continue; }

        stv.push(e);
        sons++;
        DFS(nxt, nod);
        low[nod] = min(low[nod], low[nxt]);
        if(low[nxt] >= h[nod])
        {
            art[nod] = 1;
            bcc.push_back(vector<int> ());
            int ee = stv.top();
            do
            {
                ee = stv.top();
                bcc.back().push_back(edges[ee].first);
                bcc.back().push_back(edges[ee].second);
                stv.pop();
            }while(ee != e);
        }
    }
    return sons;
}

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(i);
        edg[y].push_back(i);
        edges[i] = {x, y};
    }

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

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

    return 0;
}