Cod sursa(job #2765562)

Utilizator CelestinNegraru Celestin Celestin Data 27 iulie 2021 20:53:11
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 3.73 kb
/*#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#define maxi 36000
#define INFINITY 1000000000000
using namespace std;
using int32=int;
using int64=long long int;
using booly=bool;
ifstream f;
ofstream g;
vector<pair<int32,int32>> V[1+maxi];
priority_queue<pair<int64,int64>,vector<pair<int64,int64>>,greater<pair<int64,int64>>> heap;
booly viz[1+maxi];
int64 D[1+maxi];
int32 SURSA[1+maxi],n,m,k;
void INIT(int n)
{
    for(int i=1;i<=n;i++)
        D[i]=INFINITY;
}
void READ()
{
    int a,b,c;
    f.open("catun.in",ios::in);
    f>>n>>m>>k;
    INIT(n);
    for(int i=1;i<=k;i++)
      f>>a,heap.push(make_pair(0,a)),SURSA[a]=a,D[a]=0;
    for(int i=1;i<=m;i++)
    {
        f>>a>>b>>c;
        V[a].push_back(make_pair(b,c));
        V[b].push_back(make_pair(a,c));
    }
    f.close();
    return;
}
void DIJKSTRA()
{
    while(!heap.empty())
    {
        int k=heap.top().second;
        viz[k]=true;
        heap.pop();
        for(auto a:V[k])
        {
            int vecin=a.first;
            if(!viz[vecin])
            {
                if(D[vecin]>D[k]+a.second)
                  {
                      D[vecin]=D[k]+a.second;
                      SURSA[vecin]=SURSA[k];
                      heap.push(make_pair(D[vecin],vecin));
                  }
                else if(D[vecin]==D[k]+a.second)
                {
                    if(SURSA[k]<SURSA[vecin])
                        SURSA[vecin]=SURSA[k];
                }

            }
        }
    }
    return;
}
int main()
{
    g.open("catun.out",ios::out);
    READ();
    DIJKSTRA();
    for(int i=1;i<=n;i++)
    {
        if(i==SURSA[i])
            g<<0<<" ";
        else g<<SURSA[i]<<" ";
    }
    g.close();
    return 0;
}*/
#include <fstream>
#include <stack>
#include <vector>
#include <unordered_set>
#include <algorithm>
#define maxi 1e+5
using namespace std;
using int32=int;
using booly=bool;
ifstream cin;
ofstream cout;
unordered_set<int> S;
vector<int32> V[1+(int)maxi];
vector<int32> SOL[1+(int)maxi];
vector<int32>::iterator I1,I2;
stack<int32> stiva;
booly viz[1+(int32)maxi];
int32 tata[1+(int32)maxi],lvl[1+(int32)maxi],nma[1+(int32)maxi],n,m,cnt;
void READ()
{
    int a,b;
    cin.open("biconex.in",ios::in);
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        cin>>a>>b;
        V[a].push_back(b);
        V[b].push_back(a);
    }
    cin.close();
    return;
}
void DFS(int x)
{
    stiva.push(x);
    viz[x]=true;
    nma[x]=lvl[x];
    for(auto a:V[x])
    {
        if(viz[a]&&tata[x]!=a)///stramos in app
        {
            if(lvl[a]<nma[x])
                nma[x]=lvl[a];
        }
        if(!viz[a])
        {
            tata[a]=x;
            lvl[a]=lvl[x]+1;
            DFS(a);
            if(nma[a]<nma[x])
                nma[x]=nma[a];
            if(lvl[x]<=nma[a]&&tata[a]==x)
            {S.insert(x);
             cnt++;
             while(stiva.top()!=a)
             {
                 SOL[cnt].push_back(stiva.top());
                 stiva.pop();
             }
             SOL[cnt].push_back(a);
             stiva.pop();
             SOL[cnt].push_back(x);
            }
        }
    }
}
int main()
{
    cout.open("biconex.out",ios::out);
    READ();
    for(int i=1;i<=n;i++)
    {
        if(!viz[i])
        {
            lvl[i]=1;
            nma[i]=1;
            DFS(i);
        }
    }
    cout<<cnt<<'\n';
    for(int i=1;i<=cnt;i++)
    {
        I1=SOL[i].begin();
        I2=SOL[i].end();
        sort(I1,I2);
    }
    for(int i=1;i<=cnt;i++)
    {
        for(auto a:SOL[i])
            cout<<a<<" ";
        cout<<'\n';
    }
    cout.close();
    return 0;
}