Cod sursa(job #2674261)

Utilizator Iulia14iulia slanina Iulia14 Data 18 noiembrie 2020 21:13:51
Problema Componente biconexe Scor 64
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.64 kb
#include <fstream>
#include <vector>
using namespace std;
ifstream cin ("biconex.in");
ofstream cout ("biconex.out");
vector <int> lista[100005];
int n, m;
int daddy[100005];
int low[100005];
int dfn[100005];
int viz[100005];
struct ura{
    int x, y;
};
ura st[200005];
vector <int> comp[100005];
int cnt, k = 0, cntc;
void dfs(int nod, int ord)
{
    low[nod] = ord; ///low[u] = min(dfn[w]) unde w stramos al lui u si exista edge de la un fiu de al lui u la w
    dfn[nod] = ord; ///ordinea in dfs
    int sons = 0, i, ok = 0;
    for (i = 0; i < lista[nod].size(); i++)
    {
        int x = lista[nod][i];
        if (viz[x])
        {
            if (daddy[nod] == x)
            {
                low[nod] = min(low[nod], dfn[x]);
                continue;
            }
            if (low[nod] > dfn[x])
            {
                low[nod] = dfn[x];
                st[++k] = {nod, x};
            }
            continue;
        }
        sons++;
        viz[x] = 1;
        daddy[x] = nod;
        cnt++;
        st[++k] = {nod, x};
        dfs(x, cnt);
        low[nod] = min(low[nod], low[x]);
        if (daddy[nod] == -1 && sons > 1)
        {
            cntc++;
            while (st[k].x != nod || st[k].y != x)
            {
                comp[cntc].push_back(st[k].y);
                k--;
            }
            comp[cntc].push_back(x);
            if (comp[cntc][0] != nod)
            comp[cntc].push_back(nod);
            k--;
        }
        else
        if (low[x] >= dfn[nod] && daddy[nod] > 0)
        {
            ok = 1;
            cntc++;
            while (k && (st[k].x != nod || st[k].y != x))
            {
                comp[cntc].push_back(st[k].y);
                k--;
            }
            comp[cntc].push_back(x);
            if (comp[cntc][0] != nod)
            comp[cntc].push_back(nod);
            k--;
        }
    }
}
int main()
{
    int i;
    cin >> n >> m;
    for (i = 1; i <= m; i++)
    {
        int x, y;
        cin >> x >> y;
        lista[x].push_back(y);
        lista[y].push_back(x);
    }
    viz[1] = 1;
    cnt = 1;
    cntc = 0;
    daddy[1] = -1;
    dfs(1, 1);
    if (k)
    {
        cntc++;
        while (k > 1)
        {
            comp[cntc].push_back(st[k].y);
            k--;
        }
        comp[cntc].push_back(st[k].y);
        if (comp[cntc][0] != st[k].x)
        comp[cntc].push_back(st[k].x);
    }
    cout << cntc;
    for (i = 1; i <= cntc; i++)
    {
        cout << '\n';
        for (int j = 0; j < comp[i].size(); j++)
            cout << comp[i][j] << " ";
    }
    return 0;
}