Cod sursa(job #1931678)

Utilizator LazarAndreiLazar Andrei Teodor LazarAndrei Data 19 martie 2017 14:21:07
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.67 kb
#include <bits/stdc++.h>
using namespace std;

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

stack <pair <int, int> > stk;
vector <vector <int> >C;
vector <int> G[100005];

int Time[100005], lowTime[100005], IX, edges, nodes;

void print(int node, int it) {
    vector <int> con; int tx, ty;
    do {
        tx = stk.top().first;
        ty = stk.top().second;
        stk.pop();
        con.push_back(tx);
        con.push_back(ty);
    }
    while (tx != node || ty != it);
    C.push_back(con);
}

void DFS (int node, int parent) {
    Time[node] = IX;
    lowTime[node] = IX;
    ++ IX;

    for (auto &it: G[node]) {
        if (it == parent) continue;
        if (Time[it] == -1) {
            stk.push (make_pair (node, it));
            DFS (it, node);
            lowTime[node] = min (lowTime[node], lowTime[it]);
            if (lowTime[it] >= Time[node]) {
                print (node, it);
            }
        }
        else {
            lowTime[node] = min (lowTime[node], Time[it]);
        }
    }
}


int main()
{
    in >> nodes >> edges;
    for (int i = 1; i <= edges; ++ i) {
        int node1, node2;
        in >> node1 >> node2;
        G[node1].push_back (node2);
        G[node2].push_back (node1);
    }

    for (int i = 1; i <= nodes; ++ i) {
        Time[i] = -1;
    }
    DFS (4, 0);


    out << C.size() << "\n";
    for (size_t i = 0; i < C.size(); ++ i) {
        sort(C[i].begin(), C[i].end());
        C[i].erase(unique(C[i].begin(), C[i].end()), C[i].end());
        for (size_t j = 0; j < C[i].size(); ++ j)
            out << C[i][j] << " ";
        out << "\n";
    }
    return 0;
}