Cod sursa(job #2534044)

Utilizator stefantagaTaga Stefan stefantaga Data 29 ianuarie 2020 23:31:29
Problema Componente biconexe Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.85 kb
#include <bits/stdc++.h>

using namespace std;
ifstream f("biconex.in");
ofstream g("biconex.out");
int viz[100005],nivel[100005],low1[100005],tata[100005],rad,critic[100005],n,m,i,x,y;
vector <int> v[100005];
vector <int>  comp[100005];
stack <pair <int,int> >  deq;
int q,nr;
void dfs (int x)
{
    viz[x]=1;
    int i,nod,j;
    low1[x]=nivel[x];
    for (i=0;i<(int)v[x].size();i++)
    {
        nod=v[x][i];
        if (viz[nod]==0)
        {
            tata[nod]=x;
            nivel[nod]=nivel[x]+1;
            deq.push({x,nod});
            dfs(nod);
            if (low1[nod]<low1[x])
            {
                low1[x]=low1[nod];
            }
            if (low1[nod]>=nivel[x])
            {
                critic[x]=1;
                q++;
               while(1)
    {
        int x1 = deq.top().first;
        int y = deq.top().second;

        comp[q].push_back(x);
        comp[q].push_back(y);

        deq.pop();

        if(x1 == x || y == nod)
            break;
    }
            }
        }
        else
        {
            if (tata[x]!=nod&&low1[x]>nivel[nod])
            {
                low1[x]=nivel[nod];
            }
        }
    }
}
int 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++)
    {
        if (viz[i]==0)
        {
            nr=0;
            nivel[i]=0;
            rad=i;
            dfs(i);
        }
    }
    g<<q<<'\n';
    for (i=1;i<=q;i++)
    {
        sort (comp[i].begin(),comp[i].end());
        g<<comp[i][0]<<" ";
        for (j=1;j<comp[i].size();j++)
        {
            if (comp[i][j]!=comp[i][j-1])
            {
                g<<comp[i][j]<<" ";
            }
        }
        g<<'\n';
    }
    return 0;
}