Cod sursa(job #2883830)

Utilizator Mihai7218Bratu Mihai-Alexandru Mihai7218 Data 1 aprilie 2022 21:07:55
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.46 kb
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
int n, m, x, y, j, i, mn[100001], viz[100001];
vector <vector <int>> v, cb;
stack <pair<int, int>> s;
void cbc (int a, int b)
{
    vector <int> topush; int x, y;
    do
    {
        x = s.top().first; y = s.top().second;
        s.pop();
        topush.push_back(x); topush.push_back(y);
    } while (a != x || b != y);
    cb.push_back(topush);
}
void dfs (int x, int p, int bk)
{
    viz[x] = mn[x] = p;
    for (int i = 0; i < v[x].size(); i++)
    {
        if (v[x][i] == bk)
            continue;
        if (viz[v[x][i]] == 0)
        {
            s.push({x, v[x][i]});
            dfs (v[x][i], p+1, x);
            mn[x] = min(mn[x], mn[v[x][i]]);
            if (mn[v[x][i]] >= viz[x])
                cbc(x, v[x][i]);
        }
        else
            mn[x] = min (mn[x], viz[v[x][i]]);
    }
}
int main()
{
    fin >> n >> m; v.resize(n+1);
    for (i = 1; i <= m; i++)
    {
        fin >> x >> y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    dfs(1, 1, 0);
    fout << cb.size() << '\n';
    for (i = 0; i < cb.size(); i++, fout << "\n")
    {
        sort (cb[i].begin(), cb[i].end());
        fout << cb[i][0] << " ";
        for (j = 1; j < cb[i].size(); j++)
            if (cb[i][j-1] != cb[i][j]) fout << cb[i][j] << ' ';
    }
    return 0;
}