Cod sursa(job #2671276)

Utilizator Harsa_AndreiHarsa Andrei Harsa_Andrei Data 11 noiembrie 2020 20:52:48
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.54 kb
#include<bits/stdc++.h>


using namespace std;

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

int n, m, comp = 0, id = 1;
vector<int> M[100002];
stack<pair<int,int>> stk;
int low[100002], ids[100002], t[100002];
vector<set<int>> Solutii;

void DFS(int k)
{
    ids[k] = low[k] = id++;

    for(int y : M[k])
    {
        if(!ids[y])
        {
            t[y] = k;
            stk.push(make_pair(k, y));
            DFS(y);

            if(low[y] >= ids[k])
            {
                comp++;
                set<int> s;
                while (stk.top() != (make_pair(k, y)))
                {
                    s.insert(stk.top().first);
                    s.insert(stk.top().second);
                    stk.pop();
                }
                s.insert(stk.top().first);
                s.insert(stk.top().second);
                stk.pop();
                Solutii.push_back(s);
            }

            low[k] = min(low[k], low[y]);
        }

        else
        {
            if (y != t[k])
                low[k] = min(low[k], ids[y]);
        }
    }
}


int main()
{
    int x, y;
    fin >> n >> m;
    for(int i = 1; i <= m; i++)
    {
        fin >> x >> y;
        M[x].push_back(y);
        M[y].push_back(x);
    }

    for(int i = 1; i <= n; i++)
        if(!ids[i])
            DFS(i);

    fout << comp << '\n';
    for(int i = 0; i < comp; i++)
    {
        for(int j : Solutii[i])
            fout << j << ' ';
        fout << '\n';
    }
    return 0;
}