Cod sursa(job #1500795)

Utilizator serbanSlincu Serban serban Data 12 octombrie 2015 18:21:08
Problema Componente biconexe Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 2.13 kb
#include <bits/stdc++.h>

using namespace std;

vector<int> L[200005];
int viz[200005];
int d[200005];
int low[200005];
bool ap[200005];
deque< pair<int, int> > q;
vector< vector<int> > ret;

void dfs(int in, int depth) {
    d[in] = depth;
    low[in] = depth;
    int children = 0;
    for(int i = 0; i < L[in].size(); i ++) {
        int j = L[in][i];
        if(!viz[j]) {
            children ++;
            viz[j] = in;
            q.push_back(make_pair(j, in));
            dfs(j, depth + 1);
            low[in] = min(low[in], low[j]);
            if(viz[in] == -1 && children > 1) {
                ap[in] = true;

            }
            if(viz[in] != -1 && low[j] >= d[in]) {
                ap[in] = true;
            }
        }
        else if(j != viz[in]) {

            vector<int> aux;
            aux.clear();
            bool ok = true;
            while(!q.empty() && ok) {
                pair<int, int> punct = q.back();
                aux.push_back(punct.first);
                aux.push_back(punct.second);
                q.pop_back();
                if(punct.first == j || punct.second == j)
                    ok = false;
            }
            if(aux.size())
                ret.push_back(aux);

            if(low[in] > d[j]) {
                low[in] = d[j];
            }
        }
    }
}

int main()
{
    ifstream f("biconex.in");
    ofstream g("biconex.out");

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

    for(int i = 1; i <= n; i ++) {
        viz[i] = -1;
        dfs(i, 1);
    }
/*
    for(int i = 1; i <= n; i ++) {
        if(ap[i])
            g << i << "\n";
    }
*/
    g << ret.size() << "\n";
    for(int i = 0; i < ret.size(); i ++) {
        sort(ret[i].begin(), ret[i].end());
        if(ret[i].size())
            g << ret[i][0] << " ";
        for(int j = 1; j < ret[i].size(); j ++) {
            if(ret[i][j] != ret[i][j - 1])
                g << ret[i][j] << " ";
        }
        g << "\n";
    }
    return 0;
}