Cod sursa(job #2698934)

Utilizator razvanradulescuRadulescu Razvan razvanradulescu Data 23 ianuarie 2021 11:40:56
Problema Componente biconexe Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.15 kb
#include <fstream>
#include <stack>
#include <vector>
#include <unordered_set>
#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<unordered_set<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)
{
    sol.push_back(unordered_set<int>());
    while(!S.empty() && S.top() != targetEdge)
    {
        sol.back().insert(edges[S.top()].x);
        sol.back().insert(edges[S.top()].y);
        S.pop();
    }
    sol.back().insert(edges[S.top()].x);
    sol.back().insert(edges[S.top()].y);
    S.pop();
}

void dfs(int currNode, int parent, 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(nextNode == parent)
            continue;
        if(depth[nextNode] == 0)
        {
            S.push(graf[currNode][i]);
            dfs(nextNode, currNode, dpt + 1);
            if(lowlink[nextNode] >= depth[currNode])
            {
                popUntil(graf[currNode][i]);
            }
            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, 1);
    print();
    return 0;
}