Cod sursa(job #2808937)

Utilizator francescom_481francesco martinut francescom_481 Data 25 noiembrie 2021 18:14:21
Problema Componente biconexe Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.58 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin("biconex.in");
ofstream fout("biconex.out");
#define cin fin
#define cout fout

#define N 10000
#define mod 555557
vector < vector < int > > g, c;
stack < pair < int,int > > sk;
int x, y, n, m, dfn[N], low[N];

void scrie(int x, int y)
{
    vector < int > com;
    int tx, ty;
    do
    {
        tx = sk.top().first, ty = sk.top().second;
        sk.pop();
        com.push_back(tx);
        com.push_back(ty);
    }
    while(tx != x  ||  ty != y);
    c.push_back(com);
}
void dfs(int nod, int fnod, int nr)
{
    dfn[nod] = low[nod] = nr;
    for(int t = 0 ; t < g[nod].size() ; t++)
    {
        int z = g[nod][t];
        if(z != fnod)
        {
            if(dfn[z] == -1)
            {
                sk.push({nod,z});
                dfs(z,nod,nr+1);
                low[nod] = min(low[nod],low[z]);
                if(low[z] >= dfn[nod])scrie(nod,z);
            }
            else low[nod] = min(low[nod],dfn[z]);
        }
    }
}

int main()
{
    cin >> n >> m;
    g.resize(n+5);
    for(int i = 1 ; i <= m ; i++)
    {
        cin >> x >> y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    for(int i = 1 ; i <= n ; i++)dfn[i] = -1;
    dfs(1,0,1);
    cout << c.size() << "\n";
    for(int i = 0 ; i < c.size() ; i++)
    {
        sort(c[i].begin(),c[i].end());
        c[i].erase(unique(c[i].begin(),c[i].end()),c[i].end());
        for(auto t : c[i])
        {
            cout << t << " ";
        }
        cout << '\n';
    }
    return 0;
}