Cod sursa(job #2864154)

Utilizator alexmorosanuMorosanu Alexandru alexmorosanu Data 7 martie 2022 17:11:18
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.57 kb
#include <fstream>
#include <algorithm>
#include <stack>
#include <vector>
using namespace std;
ifstream f("biconex.in");
ofstream g("biconex.out");
vector <vector<int>> S;
vector <int> v[100011];
stack <pair<int,int>> q;
void component(int x,int y)
{
    vector <int> s;
    int ix,iy;
    do
    {
        ix=q.top().first;
        iy=q.top().second;
        s.push_back(ix);
        s.push_back(iy);
        q.pop();
    }while(ix!=x && iy!=y);
    S.push_back(s);
}
int when[100011],low[100011],part[100011];
void dfs(int nod,int tata,int k)
{
    when[nod]=low[nod]=k;
    for(int i=0;i<v[nod].size();i++)
    {
        if(v[nod][i]==tata)
            continue;
        if(when[v[nod][i]]==-1)
        {
             q.push(make_pair(nod,v[nod][i]));
             dfs(v[nod][i],nod,k+1);
             low[nod]=min(low[nod],low[v[nod][i]]);
             if(low[v[nod][i]]>=when[nod])
             {
                part[nod]++;
                component(nod,v[nod][i]);
             }
        }
        else
            low[nod]=min(low[nod],when[v[nod][i]]);
    }
}
int n,m,x,y,i,j;
int main()
{
    f>>n>>m;
    for(i=1;i<=m;i++)
    {
        f>>x>>y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    for(i=1;i<=n;i++)
        when[i]=-1;
    dfs(1,0,0);
    g<<S.size()<<'\n';
    for(i=0;i<S.size();i++)
    {
        sort(S[i].begin(),S[i].end());
        g<<S[i][0]<<" ";
        for(j=1;j<S[i].size();j++)
            if(S[i][j]!=S[i][j-1])
            g<<S[i][j]<<" ";
        g<<'\n';
    }
    return 0;
}