Cod sursa(job #2123501)

Utilizator alexilasiAlex Ilasi alexilasi Data 6 februarie 2018 12:19:47
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.31 kb
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>
#define nmax 100001
using namespace std;
ifstream f("biconex.in");
ofstream g("biconex.out");
vector <int> v[nmax];
stack <pair<int,int> > s;
int t[nmax],viz[nmax],low[nmax],niv[nmax],r,sol[nmax],sl[nmax],nr,n,m,x,y,num;
void df(int i)
{
    viz[i]=1;
    low[i]=niv[i];
    for(int j=0; j<v[i].size(); j++)
    {
        if(v[i][j]!=t[i]&&niv[i]>niv[v[i][j]])
            s.push({i,v[i][j]});
        if(!viz[v[i][j]])
        {
            niv[v[i][j]]=niv[i]+1;
            t[v[i][j]]=i;
            df(v[i][j]);
            low[i]=min(low[i],low[v[i][j]]);
            if(low[v[i][j]]>=niv[i])
            num++;
        }
        else if(v[i][j]!=t[i]) low[i]=min(low[i],niv[v[i][j]]);
    }
}
void df2(int i)
{
    viz[i]=1;
    low[i]=niv[i];
    for(int j=0; j<v[i].size(); j++)
    {
        if(v[i][j]!=t[i]&&niv[i]>niv[v[i][j]])
            s.push({i,v[i][j]});
        if(!viz[v[i][j]])
        {
            niv[v[i][j]]=niv[i]+1;
            t[v[i][j]]=i;
            df2(v[i][j]);
            low[i]=min(low[i],low[v[i][j]]);
            if(low[v[i][j]]>=niv[i])
            {
               int k=0;
                do{
                x=s.top().first;
                y=s.top().second;
                s.pop();
                sol[++k]=x;
                sol[++k]=y;
                }while(!s.empty()&&(x!=i||y!=v[i][j])&&(y!=i||x!=v[i][j]));
            sort(sol+1,sol+k+1);
            for(int j1=1;j1<=k;j1++)
                if(sol[j1]!=sol[j1-1]) g<<sol[j1]<<' ';
            g<<'\n';
            }
        }
        else if(v[i][j]!=t[i]) low[i]=min(low[i],niv[v[i][j]]);
    }
}
int main()
{
    int i;
    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])
        {
            r=i;
            nr=0;
            niv[i]=1;
            df(i);
            if(nr>1) sol[r]=1;
            else sol[r]=0;
        }
    g<<num<<'\n';
    for(i=1;i<=n;i++) viz[i]=niv[i]=low[i]=t[i]=0;
    for(i=1; i<=n; i++)
        if(!viz[i])
        {
            r=i;
            nr=0;
            sl[++num]=i;
            niv[i]=1;
            df2(i);
        }
    return 0;
}