Cod sursa(job #2498225)

Utilizator cyg_vladioanBirsan Vlad cyg_vladioan Data 23 noiembrie 2019 17:29:58
Problema Componente biconexe Scor 56
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.87 kb
#include <cstdio>
#include <vector>
#include <set>
#define u first
#define v second
using namespace std;
const int NMAX = 100000;
const int MMAX = 200000;
typedef pair <int , int> ii;
vector <int> G[NMAX + 5];
set <int> s[NMAX + 5];
ii st[MMAX];
int dfn[NMAX + 5] , low[NMAX + 5] , nrcomp , top , ord , start;
void comp_biconexa(int u , int v)
{
    nrcomp ++;
    ii aux;
    do
    {
        aux = st[top];
        if(s[nrcomp].find(aux.u) == s[nrcomp].end())
            s[nrcomp].insert(aux.u);
        if(s[nrcomp].find(aux.v) == s[nrcomp].end())
            s[nrcomp].insert(aux.v);
        top --;
    }
    while(aux.u != u && aux.v != v);
}
void dfs(int u , int tu)
{
    int v , j;
    ord ++;
    dfn[u] = low[u] = ord;
    for(j = 0 ; j < G[u].size() ; j ++)
    {
        v = G[u][j];
        if(v != tu && dfn[v] < dfn[u])
        {
            top ++;
            st[top].u = u;
            st[top].v = v;
        }
        if(dfn[v] == -1)
        {
            dfs(v , u);
            low[u] = min(low[u] , low[v]);
            if(low[v] >= dfn[u])
                comp_biconexa(u , v);
        }
        else if(v != tu)
            low[u] = min(low[u] , dfn[v]);
    }
}
int main()
{
    freopen("biconex.in" , "r" , stdin);
    freopen("biconex.out" , "w" , stdout);
    int n , m , u , v , i;
    scanf("%d%d" , &n , &m);
    for(i = 1 ; i <= m ; i ++)
    {
        scanf("%d%d" , &u , &v);
        G[u].push_back(v);
        G[v].push_back(u);
    }
    for(i = 1 ; i <= n ; i ++)
        dfn[i] = low[i] = -1;
    top = 1;
    st[1].u = -1;
    st[1].v = 1;
    dfs(1 , -1);
    set <int>::iterator it;
    printf("%d\n" , nrcomp);
    for(i = 1 ; i <= nrcomp ; i ++)
    {
        for(it = s[i].begin() ; it != s[i].end() ; it ++)
            printf("%d " , (*it));
        printf("\n");
    }
    return 0;
}