Cod sursa(job #2648132)

Utilizator Tudor_PascaTudor Pasca Tudor_Pasca Data 8 septembrie 2020 20:51:34
Problema Componente biconexe Scor 12
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.91 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>

using namespace std;

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

int n, m, ansCount;
int low[100100], level[100100];
bool fr[100100];
vector<vector<int>> adj, ans;
stack<int> s;

void addAns(int stopper)
{
    //cout << "THIS IS STOPPER:  " <<  stopper << '\n';

    while(s.top() != stopper)
    {
        ans[ansCount].push_back(s.top());
        s.pop();
    }

    ans[ansCount].push_back(s.top());

}

void solve(int node, int father)
{
    fr[node] = true;
    level[node] = level[father] + 1;
    low[node] = level[father];

    int sons = 0;

    //cout << node << '\n';

    s.push(node);

    for(auto it : adj[node])
    {
        if(it == father)
            continue;

        //cout << node << ' ' << it << '\n';

        if(fr[it] == true)
            low[node] = min(low[node], level[it]);
        else
        {
            solve(it, node);

            //cout << "AFTER LOOP:  " << node << ' ' << it << '\n';
            //cout << "AFTER LOOP LEVEL:  " << level[node] << ' ' << low[it] << '\n';

            if(level[node] <= low[it])
            {
                ansCount++;

                ans.resize(ansCount + 5);

                addAns(node);
            }

            low[node] = min(low[node], low[it]);
        }
    }

    if(father == 0 && sons > 1)
    {
        ansCount++;
        addAns(node);
    }
}

int main()
{
    in >> n >> m;

    adj.resize(n + 5);

    for(int i = 1; i <= m; i++)
    {
        int x, y;
        in >> x >> y;

        adj[x].push_back(y);
    }

    solve(1, 0);

    out << ansCount << '\n';

    for(int i = 1; i <= ansCount; i++)
    {
        int len = ans[i].size();

        for(int j = 0; j < len; j++)
            out << ans[i][j] << ' ';

        out << '\n';
    }

    return 0;
}