Cod sursa(job #2686541)

Utilizator Danut200333Dumitru Daniel Danut200333 Data 19 decembrie 2020 11:36:26
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.65 kb
#include <fstream>
#include <vector>
#include <stack>

using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
int n, m, i, j, a[100005], min1[100005];
bool viz[100005];
vector <int> v[100005], t(100005, -1);
vector <vector <int> > sol;
stack<int> st;
void dfs(int nod)
{
    int i, x;
    vector<int> c;
    viz[nod] = true;
    a[nod] = a[t[nod]] + 1;
    min1[nod] = a[nod];
    st.push(nod);
    for(i = 0; i < v[nod].size(); i++)
        if(viz[v[nod][i]])
        {
            if(v[nod][i] != t[nod])min1[nod] = min(min1[nod], a[v[nod][i]]);
        }
        else
        {
            t[v[nod][i]] = nod;
            dfs(v[nod][i]);
            min1[nod] = min(min1[nod], min1[v[nod][i]]);
            if(a[nod] <= min1[v[nod][i]])
            {
                c.clear();
                while(!st.empty())
                {
                    x = st.top();
                    st.pop();
                    c.push_back(x);
                    if(x == v[nod][i])
                    {
                        c.push_back(nod);
                        sol.push_back(c);
                        break;
                    }
                }
            }
        }
}
int main()
{
    fin>>n>>m;
    while(m)
    {
        fin>>i>>j;
        v[i].push_back(j);
        v[j].push_back(i);
        m--;
    }
    for(i = 1; i <= n; i++)
        if(!a[i])
        {
            t[i] = 0;
            dfs(i);
        }
    fout<<sol.size()<<'\n';
    for(i=0;i<sol.size();i++)
    {
        for(j=0;j<sol[i].size();j++)fout<<sol[i][j]<<" ";
        fout<<'\n';
    }


    return 0;
}