Cod sursa(job #1970048)

Utilizator dumbraveanbDumbravean Bogdan dumbraveanb Data 18 aprilie 2017 20:30:01
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.59 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>

using namespace std;

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

#define inf 0x3f3f3f3f

int n, m, a, b, idx, k;

vector<vector<int>> G, cc;
vector<int> L, Idx, c;
stack<pair<int, int>> Stk;

void Save(int x, int y) {
    c.clear();
    int nodx, nody;

    do {
        nodx = Stk.top().first;
        nody = Stk.top().second;
        c.push_back(nodx);
        c.push_back(nody);
        Stk.pop();
    } while(nodx != x || nody != y);
    sort(c.begin(), c.end());
    c.erase(unique(c.begin(), c.end()), c.end());
    cc.push_back(c);
}

void Tarjan(const int& nod, const int& t) {
    Idx[nod] = L[nod] = idx++;

    for(const int& y : G[nod])
        if(Idx[y] == inf) {
            Stk.push({nod, y});
            Tarjan(y, nod);
            L[nod] = min(L[nod], L[y]);
            if(L[y] >= Idx[nod])
                Save(nod, y);
        } else
            if(y != t)
                L[nod] = min(L[nod], Idx[y]);
}

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

    G = vector<vector<int>> (n + 1);
    L = vector<int> (n + 1);
    Idx = vector<int> (n + 1, inf);

    for(int i = 1; i <= m; ++i) {
        fin >> a >> b;
        G[a].push_back(b);
        G[b].push_back(a);
    }

    for(int i = 1; i <= n; ++i)
        if(Idx[i] == inf)
            Tarjan(i, 0);

    fout << cc.size() << '\n';

    for(int i = 0; i < cc.size(); ++i) {
        for(int x : cc[i])
            fout << x << ' ';
        fout << '\n';
    }
    return 0;
}