Cod sursa(job #2698884)

Utilizator razvanradulescuRadulescu Razvan razvanradulescu Data 23 ianuarie 2021 11:06:38
Problema Componente biconexe Scor 48
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.63 kb
#include <fstream>
#include <stack>
#include <vector>
#define MAX_NODES 100005
#define MAX_EDGES 200005
using namespace std;

ifstream f("biconex.in");
ofstream g("biconex.out");

struct edge
{
    int x, y;
    bool viz;

    int opposite(int nr)
    {
        if(x == nr)
            return y;
        return x;
    }

    void init(int x, int y)
    {
        this->x = x;
        this->y = y;
    }
} edges[MAX_EDGES];

vector<int> graf[MAX_NODES];
int n, m;
int lowlink[MAX_NODES];
int depth[MAX_NODES];
stack<int> S;
vector<vector<int> >sol;

void read()
{
    f>>n>>m;
    int x, y;
    for(int i = 0; i<m; i++)
    {
        f>>x>>y;
        edges[i].init(x, y);
        graf[x].push_back(i);
        graf[y].push_back(i);
    }
}

void popUntil(int targetEdge)
{
    vector<int> currSol;
    if(targetEdge == S.top())
    {
        currSol.push_back(edges[targetEdge].x);
        currSol.push_back(edges[targetEdge].y);
        S.pop();
    }
    else
    {
        int lastEdge;
        if(depth[edges[targetEdge].x] < depth[edges[targetEdge].y])
            lastEdge = edges[targetEdge].x;
        else
            lastEdge = edges[targetEdge].y;
        while(!S.empty() && S.top() != targetEdge)
        {
            lastEdge = edges[S.top()].opposite(lastEdge);
            S.pop();
            currSol.push_back(lastEdge);
        }
        lastEdge = edges[targetEdge].opposite(lastEdge);
        S.pop();
        currSol.push_back(lastEdge);
    }
    sol.push_back(currSol);
}

void dfs(int currNode, int dpt)
{
    depth[currNode] = dpt;
    lowlink[currNode] = dpt;
    for(int i = 0; i<graf[currNode].size(); i++)
    {
        int nextNode = edges[graf[currNode][i]].opposite(currNode);
        if(edges[graf[currNode][i]].viz)
            continue;
        edges[graf[currNode][i]].viz = true;
        S.push(graf[currNode][i]);
        if(depth[nextNode] == 0)
        {
            dfs(nextNode, dpt + 1);
            if(lowlink[nextNode] >= depth[currNode])
            {
                popUntil(graf[currNode][i]);
            }
        }
        if(depth[nextNode] > depth[currNode])
        {
            if(lowlink[nextNode] < lowlink[currNode])
                lowlink[currNode] = lowlink[nextNode];
        }
        else
            lowlink[currNode] = min(lowlink[currNode], depth[nextNode]);
    }
}

void print()
{
    g<<sol.size()<<"\n";
    for(auto p : sol)
    {
        for(auto i : p)
        {
            g<<i<<" ";
        }
        g<<"\n";
    }
}

int main()
{
    read();
    dfs(1, 1);
    print();
    return 0;
}