Cod sursa(job #1500813)

Utilizator serbanSlincu Serban serban Data 12 octombrie 2015 18:39:36
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.99 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;

                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 == in || punct.second == in)
                        ok = false;
                }
                if(aux.size())
                    ret.push_back(aux);

            }
            if(viz[in] != -1 && low[j] >= d[in]) {
                ap[in] = true;
                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 == in || punct.second == in)
                        ok = false;
                }
                if(aux.size())
                    ret.push_back(aux);
            }
        }
        else if(j != viz[in]) {
            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);
        vector<int> aux;
        aux.clear();
        while(!q.empty()) {
            pair<int, int> punct = q.back();
            aux.push_back(punct.first);
            aux.push_back(punct.second);
            q.pop_back();
        }
        if(aux.size())
            ret.push_back(aux);
    }
/*
    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;
}