Cod sursa(job #2820883)

Utilizator MenelausSontea Vladimir Menelaus Data 21 decembrie 2021 20:18:27
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.39 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>
#include <set>

std::ifstream in("biconex.in");
std::ofstream out("biconex.out");

const int N=100000;
const int M=200000;

struct edge
{
    int from;
    int to;
};

std::vector<int> v[N+1];
std::vector<std::vector<int>> ans;

edge muchii[M+1];
std::stack<int> q;

int timp=0;

int t[N+1];
int low[N+1];
int parent[N+1];
int children[N+1];

void Dfs(int i)
{
    t[i]=low[i]=++timp;

    for(int edg : v[i])
    {
        int copil=muchii[edg].from+muchii[edg].to-i;

        if(!t[copil])
        {
            //std::cout<<i<<" "<<copil<<"\n";

            q.push(edg);
            children[i]++;
            parent[copil]=i;
            Dfs(copil);
            low[i]=std::min(low[i], low[copil]);

            if(parent[i]==0 && children[i]>1)
            {
                std::vector<int> prov;

                while(q.top()!=edg)
                {
                    prov.push_back(q.top());
                    q.pop();
                }
                prov.push_back(q.top());
                q.pop();

                ans.push_back(prov);
            }
            if(parent[i]!=0 && low[copil]>=t[i])
            {
                std::vector<int> prov;

                while(q.top()!=edg)
                {
                    prov.push_back(q.top());
                    q.pop();
                }
                prov.push_back(q.top());
                q.pop();

                ans.push_back(prov);
            }
        }
        else if(parent[i]!=copil)
        {
            low[i]=std::min(low[i], t[copil]);
        }
    }
}

int main()
{
    int n, m, x, y;

    in>>n>>m;
    for(int i=1; i<=m; i++)
    {
        in>>x>>y;
        muchii[i].from=x;
        muchii[i].to=y;
        v[x].push_back(i);
        v[y].push_back(i);
    }

    Dfs(1);

    std::vector<int> prov;
    while(!q.empty())
    {
        prov.push_back(q.top());
        q.pop();
    }
    ans.push_back(prov);

    out<<ans.size()<<"\n";
    for(auto cnt : ans)
    {
        std::set<int> temp;
        for(int i : cnt)
        {
            temp.insert(muchii[i].from);
            temp.insert(muchii[i].to);
        }

        for(auto p : temp)
        {
            out<<p<<" ";
        }
        out<<"\n";
    }
}